LeetCode 熱題 100 | 101. 對稱二叉樹

大家好，今天我們來解決一道經典的二叉樹問題——對稱二叉樹。這道題在 LeetCode 上被標記為簡單難度，要求檢查給定的二叉樹是否軸對稱。

---

問題描述

給你一個二叉樹的根節點 root，檢查它是否軸對稱。

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

提示：

• 樹中節點數目在范圍 [1, 1000] 內
• -100 <= Node.val <= 100

---

解題思路

核心思想

1. 遞歸法：

   • 使用遞歸法檢查二叉樹是否對稱。
   • 對于兩個子樹，如果它們的根節點值相等，并且左子樹的左子樹與右子樹的右子樹對稱，左子樹的右子樹與右子樹的左子樹對稱，則這兩個子樹對稱。

2. 遞歸函數：

   • 定義一個輔助函數 isSymmetric，用于檢查兩個子樹是否對稱。

---

Python代碼實現

class Solution:def isSymmetric(self, root: TreeNode) -> bool:if not root:return Truedef isMirror(left: TreeNode, right: TreeNode) -> bool:if not left and not right:return Trueif not left or not right:return Falsereturn (left.val == right.val) and isMirror(left.left, right.right) and isMirror(left.right, right.left)return isMirror(root.left, root.right)

代碼解析

1. 基本情況：

   • 如果根節點為空，直接返回 True，因為空樹是對稱的。

2. 遞歸函數：

   • 定義一個輔助函數 isMirror，用于檢查兩個子樹是否對稱。
   • 如果兩個子樹都為空，返回 True。
   • 如果一個子樹為空，另一個不為空，返回 False。
   • 如果兩個子樹的根節點值相等，并且左子樹的左子樹與右子樹的右子樹對稱，左子樹的右子樹與右子樹的左子樹對稱，則返回 True。

3. 遞歸調用：

   • 調用 isMirror 函數，檢查根節點的左子樹和右子樹是否對稱。

---

復雜度分析

• 時間復雜度：O(n)，其中 n 是樹中節點的數量。每個節點被訪問一次。
• 空間復雜度：O(h)，其中 h 是樹的高度。遞歸調用棧的深度最多為樹的高度。

---

示例運行

示例 1

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2

輸入：root = [1,2,2,null,3,null,3]
輸出：false

---

總結

通過遞歸法，我們可以高效地檢查二叉樹是否對稱。遞歸函數 isMirror 用于比較兩個子樹是否對稱，確保每個節點的值和結構都符合對稱條件。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！