---
title: "100. Same Tree"
url: "https://laigary.com/interview/coding/100-same-tree"
type: "note"
section: "coding"
date: "2026-07-24"
updated: "2026-07-26"
tags: ["Tree", "Breadth-First Search", "Depth-First Search"]
---

# 100. Same Tree

[100\. Same Tree](https://leetcode.com/problems/same-tree/)

判斷兩棵二元樹是否完全相同（結構一樣、對應位置的值也一樣）。

## 思路

這題的核心是**兩棵樹同步走**：不是各自走完再比對，而是每一步都同時拿著 `p` 和 `q` 的對應節點往下。

只要想清楚遞迴的三種情況就寫完了：

1. **兩邊都是 `None`** → 走到底了，這一支相同 → `True`
2. **只有一邊是 `None`，或值不一樣** → 結構或內容不同 → `False`
3. **兩邊都在且值相同** → 還不能下結論，繼續比左右子樹，**兩邊都要相同**才算相同

順序很重要：**先判兩邊都空，再判其中一邊空**。反過來寫的話「兩邊都空」會被誤判成 `False`。

第 3 步用 `and` 連接左右，代表**任何一邊不同就整棵不同** —— 而且 Python 的 `and` 會短路，左邊發現不同就不會再走右邊，等於免費的剪枝。

## 解題方向

### 遞迴（同步 DFS）

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left)  and self.isSameTree(p.right, q.right)
```

三行對應上面三種情況，這是最好記的寫法。

### 迭代（用佇列成對比較）

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:   
        queue = deque([(p, q)])
        
        while queue:
            a, b = queue.popleft()
            if a and b and a.val == b.val:
                queue.extend([(a.left, b.left), (a.right, b.right)])
            elif a or b:
                return False
        
        return True
```

**佇列裡放的是「一對節點」而不是單一節點** —— 這是同步遍歷的關鍵，把「兩棵樹一起走」直接編碼進資料結構裡。

三種情況在這裡對應成：`if` 是「都在且相同 → 繼續」，`elif a or b` 是「只有一邊在 → 不同」，兩者都不成立（都是 `None`）就什麼都不做、繼續處理佇列裡的下一對。

不想用遞迴時就是這個寫法。

## 補充

**這題是 [572. Subtree of Another Tree](/interview/coding/572-subtree-of-another-tree) 的子程序。** 那題要判斷 `subRoot` 是不是 `root` 的某棵子樹，做法就是「對 `root` 的每個節點呼叫一次本題的比較函式」。先把這題寫熟，572 只是多一層外圈。

**相關的同步遍歷題**：[226. Invert Binary Tree](/interview/coding/226-invert-binary-tree)（反轉後和原本比較，就是判斷對稱）、[106. Construct Binary Tree from Inorder and Postorder Traversal](/interview/coding/106-construct-binary-tree-from-inorder-and-postorder-traversal)。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。

## 複雜度

**遞迴**
- 時間 $O(\min(m, n))$ — 一發現不同就短路返回，最多走完比較小的那棵樹
- 空間 $O(\min(m, n))$ — 遞迴堆疊，最壞情況是兩棵都退化成鏈

**迭代**
- 時間 $O(\min(m, n))$ — 同上
- 空間 $O(\min(m, n))$ — 佇列裡最多裝下一層的節點對

其中 `m`、`n` 是兩棵樹的節點數。常見的寫法是寫 $O(n)$，但嚴格說是取兩者的最小值 —— 因為只要有一邊先走完或先發現不同就結束了。