100. Same Tree

──────────────────────────────────────────────────────────────────────

100. Same Tree

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

思路

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

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

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

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

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

解題方向

遞迴（同步 DFS）

# 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)

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

迭代（用佇列成對比較）

# 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 的子程序。 那題要判斷 subRoot 是不是 root 的某棵子樹，做法就是「對 root 的每個節點呼叫一次本題的比較函式」。先把這題寫熟，572 只是多一層外圈。

相關的同步遍歷題：226. Invert Binary Tree（反轉後和原本比較，就是判斷對稱）、106. Construct Binary Tree from Inorder and Postorder Traversal。整理見 Tree 遍歷模板。

複雜度

遞迴

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

迭代

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

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