1 題目描述



檢查兩棵樹是否相同

2 解法

這題跟101-Symmetric Tree的解法很像，所以很簡單：
一樣套用 Recursion 的思維，我們先將大問題變成小問題

  1. 大問題：知道兩個樹是否相同
  2. 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹是對稱的。
  3. 大小關係式：(p.val == q.val) and (p.left, q.left) and (p.right, q.left)
    1. 當前的值相同 and 左子樹相同 and 右子樹相同
  4. 最小的問題：當 p 和 q 都觸底的時候，是如果都是None就代表True，但是當其中一邊有值，另一邊沒有值，就不相同了。
1
2
3
4
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q: return True
    if not p or not q: return False
    return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

3 總結

這題很簡單，跟檢查兩棵樹是否對稱有一樣的解法，所以四分鐘就解完通過了！果然武器還是要備好。