LeetCode 101. 對稱二叉樹 - 力扣【難度：簡單；通過率：62.6%】，這道題與前一題：LeetCode100 基本相似，都是遞歸的思路，解法可以對照參考上一篇博文： leetcode100.相同的樹（遞歸練習題）

一、 題目描述

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

示例:

示例 1:

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

示例 2:

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

---

二、 核心思路：判斷左右子樹是否互為鏡像

一棵樹是否對稱，其本質在于：它的左子樹和右子樹是否互為鏡像

因此，我們可以將問題分解為：

1. 從根節點開始，判斷其左子樹和右子樹是否互為鏡像
2. 遞歸地，對于任意一對需要判斷是否互為鏡像的節點 left 和 right：
   • left 的左孩子，應該與 right 的右孩子互為鏡像
   • left 的右孩子，應該與 right 的左孩子互為鏡像

---

三、 遞歸的終止條件 (Base Cases)

在遞歸函數中，正確處理基準情況是關鍵。對于判斷兩個節點是否互為鏡像，有以下幾種情況：

• 情況一：兩個節點都為空
  • 如果 left 和 right 都為 null，它們是鏡像的。返回 true
• 情況二：只有一個節點為空
  • 如果 left 為 null 而 right 不為 null，或者 left 不為 null 而 right 為 null，它們不可能是鏡像的。返回 false
• 情況三：兩個節點都不為空，但值不同
  • 如果 left 和 right 都不為 null，但 left.val != right.val，它們的值不同，因此不互為鏡像。返回 false

---

四、 代碼實現與深度解析

【一種參考代碼】：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 主入口函數：判斷整棵樹是否對稱，即判斷其左子樹和右子樹是否互為鏡像public boolean isSymmetric(TreeNode root) {// 如果根節點為空，根據定義，空樹也是對稱的if (root == null) {return true;}// 調用輔助函數，判斷根節點的左右孩子是否互為鏡像return isMirror(root.left, root.right);}/*** 輔助遞歸函數：判斷兩棵子樹（以 left 和 right 為根）是否互為鏡像* @param left  第一棵子樹的根節點* @param right 第二棵子樹的根節點* @return 如果兩棵子樹互為鏡像，則返回 true；否則返回 false*/public boolean isMirror(TreeNode left, TreeNode right) {// 1. 基準情況一：兩個節點都為空，它們互為鏡像if (left == null && right == null) {return true;}// 2. 基準情況二：只有一個節點為空（由于是 else if，排除了都為空的情況）// 此時，一個為空，一個不為空，肯定不互為鏡像else if (left == null || right == null) {return false;}// 3. 基準情況三：兩個節點都不為空，但值不相等，不互為鏡像else if (left.val != right.val) {return false;}// 4. 遞歸調用：// 如果以上基準情況都未命中（即 left 和 right 都不為空且值相等），// 則繼續遞歸判斷它們的子節點是否互為鏡像// 關鍵點：left 的左孩子要與 right 的右孩子比較 (isMirror(left.left, right.right))//         left 的右孩子要與 right 的左孩子比較 (isMirror(left.right, right.left))// 只有這兩對都互為鏡像，當前這對節點才算互為鏡像return isMirror(left.left, right.right) && isMirror(left.right, right.left);}
}

---

五、 關鍵點與復雜度分析

• 函數職責分離：isSymmetric 負責初始調用，isMirror 負責具體的遞歸判斷。這種分離使得代碼邏輯更清晰
• 對稱性體現：遞歸調用 isMirror(left.left, right.right) 和 isMirror(left.right, right.left) 是本題的核心，它完美地體現了鏡像對稱的定義
• Base Case 的全面性：對三種基準情況的清晰劃分，確保了遞歸的正確終止和各種邊界條件的覆蓋
• 時間復雜度：O(N) 其中 N 是二叉樹的節點數。每個節點最多被訪問一次（通過 isMirror 函數中的 left 或 right 參數），進行常數次比較操作
• 空間復雜度：O(H) 其中 H 是二叉樹的高度。這主要是遞歸調用棧的空間開銷。最壞情況下（樹退化為鏈表），H 可以達到 N，所以空間復雜度為 O(N)

---

六、 總結與對比 (LC100 vs LC101)

特性	LeetCode 100 (相同的樹)	LeetCode 101 (對稱二叉樹)
問題定義	判斷兩棵獨立的樹 p 和 q 是否結構和值都相同	判斷一棵樹 root 是否自身鏡像對稱
遞歸入口	isSameNode(p, q)	isMirror(root.left, root.right)
遞歸調用	isSameNode(p.left, q.left) 和 isSameNode(p.right, q.right)	isMirror(left.left, right.right) 和 isMirror(left.right, right.left)
核心差異	同向比較：左對左，右對右	交叉比較：左的左對右的右，左的右對右的左