我們之前深入了解鏈結串列。今天，我們學習「樹」這種複雜的資料結構。

題目連結: 100. Same Tree

題目描述:給你兩棵二元樹的根節點 p 和 q，判斷兩棵樹是否相同。

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2,1], q = [1,1,2]
Output: false

Python

解題思路:
處理樹的問題，最自然的思考方式就是 遞迴。我們可以把一個大問題（判斷整棵樹是否相同）分解成數個小問題（判斷當前節點和它們的子樹是否相同）。

isSameTree(p, q) 需要回答一個問題：「p 和 q 這兩個節點以及它們代表的子樹是否相同？」

1. 兩個節點都是 None

   • 如果 p 和 q 同時都是 None，代表我們同時走到了兩棵樹的葉子節點下面。return True。

2. 其中一個節點是 None，另一個不是

   • 說明兩棵樹的結構在這裡出現了分歧，一個有節點，一個沒有。return False。

3. 兩個節點都不是 None，但它們的值不相等

   • 如果 p.val != q.val，那即使結構一樣，值也不同。return False。

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None or q ==None:
            if p == q:
                return True
            else:
                return False
        return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

演算法分析:

• 如果以上三種情況都沒有發生，說明 p 和 q 都不是 None，且值相等。
• and self.isSameTree(p.left,q.left)如果當前節點的值相等，就繼續遞迴地檢查它們的左子樹是否也相同。如果左子樹不同，遞迴呼叫會返回 False，and 鏈同樣會中斷。
• and self.isSameTree(p.right,q.right)如果左子樹也相同，就做最後一步檢查：遞迴地檢查它們的右子樹是否也相同。
• 當以上所有三個條件都為 True 時，代表以 p 和 q 為根的這兩棵子樹是完全相同的。

複雜度分析:

• 時間複雜度為 O(n)。

  1. 在最壞的情況下，我們需要完整地遍歷兩棵樹的所有節點一次，來確認它們是否相同。
  2. n 是兩棵樹中節點數較少的那個。

• 空間複雜度： O(n)。

  1. 空間消耗主要來自於遞迴呼叫的堆疊 。
  2. 堆疊的深度取決於樹的高度n。
  3. 平均情況（樹是Avg Tree），空間複雜度是 O(log n)。
  4. 最壞情況（樹極度不平衡，退化成鏈結串列），空間複雜度是 O(n)。

有問題可以底下留言!
下回見!!