0100. Same Tree - chasel2361/leetcode GitHub Wiki

?Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:
Input: [1,2,3], [1,2,3]
Output: true

Example 2:
Input: [1,2], [1,null,2]
Output: false

Example 3:
Input: [1,2,1], [1,1,2]
Output: false

終於到了大名鼎鼎的二元樹啦，二元樹的簡介在這邊，這個問題要求判定兩棵二元樹是否相等，所以必須將兩棵樹完全走過一遍才能確認是否相同，但二元樹可以很大很複雜，所以不能盲目亂走，需要有個方法。

走訪整棵樹的方法有前序、中序、後序以及層序四種，這邊我們使用前序，也就是

"根 → 左子樹 → 右子樹"

的順序，當這三者都相等的時候，我們才可以確認這兩棵二元樹完全相等，此處使用遞迴法

[1] p 及 q 皆不存在也表示相等
[2] 若 p, q 僅有一者存在，則表示不相等
[3] 依照前述的前序遍歷以遞迴法檢查二元樹是否相等

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q: return True # [1]
        if (p and not q) or (q and not p): return False # [2]
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) # [3]

這樣寫的時間複雜度是 O(N), 空間複雜度為 O(N)