今天我們來加深對樹的遞迴思想的理解。

題目連結: 101. Symmetric Tree

題目描述:給你一個二元樹的根節點 root，請檢查它是否對稱。

Input: root = [1,2,2,3,4,4,3]
Output: true

Input: root = [1,2,2,null,3,null,3]
Output: false

Python

解題思路:
這個問題的核心思想和昨天的 Same Tree 非常相似，都是用遞迴來解決。但是，比較的對象發生了變化。

在 Same Tree 中，我們比較的是 p.left 和 q.left，p.right 和 q.right。

而在 Symmetric Tree 中，要判斷是否為鏡像，我們需要比較的是：

樹的左子樹 和 樹的右子樹 是否互為鏡像。

更進一步地，對於任意兩個要比較是否為鏡像的節點 node1 和 node2：

它們的值必須相等 (node1.val == node2.val)。

node1 的左子樹必須和 node2 的右子樹互為鏡像。

node1 的右子樹必須和 node2 的左子樹互為鏡像。

class Solution:
    def ismirror(self, root1: Optional[TreeNode],root2: Optional[TreeNode]) -> bool:
        if root1 == None or root2 == None:
            if root1 == root2:
                return True
            else:
                return False
        return root1.val == root2.val and self.ismirror(root1.left,root2.right) and self.ismirror(root.right,root2.left)
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.ismirror(root.left,root.right)

演算法分析:

• 創建一個輔助函式isMirror，來判斷這兩個節點代表的子樹是否互為鏡像，終止情況如下:
  1. 如果 node1 和 node2 都是 None，代表這條路徑是對稱的，返回 True。
  2. 如果 node1 和 node2 其中一個是 None（另一個不是），代表結構不對稱，返回 False。
  3. 如果 node1 和 node2 的值不相等 (node1.val != node2.val)，它們肯定不對稱，返回 False。
• 遞迴地檢查它們的子樹是否也「交叉對稱」。
• 在主函式 isSymmetric 中，我們只需要檢查根節點 root 的左右子樹是否互為鏡像即可。直接呼叫 isMirror(root.left, root.right)。

複雜度分析:

• 時間複雜度為 O(n)(我們需要遍歷樹中的每一個節點一次，n 是樹的總節點數)。
• 空間複雜度： O(n)。
  1. 空間消耗主要來自於遞迴呼叫的堆疊 。
  2. 堆疊的深度取決於樹的高度n。
  3. 平均情況（樹是Avg Tree），空間複雜度是 O(log n)。
  4. 最壞情況（樹極度不平衡，退化成鏈結串列），空間複雜度是 O(n)。

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