101. Symmetric Tree

題目 / Problem

給定一棵二元樹的根節點 root，請判斷這棵樹是否為「鏡像對稱」——也就是說，把它從正中間畫一條垂直線，左半邊和右半邊是否互為鏡像。

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Constraints / 限制 - 節點數量在 [1, 1000] 之間 / The number of nodes is in the range [1, 1000]. - -100 <= Node.val <= 100

Example / 範例

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

這棵樹長這樣 / The tree looks like:

        1
       / \
      2   2
     / \ / \
    3  4 4  3

左子樹 2(3,4) 和右子樹 2(4,3) 剛好是鏡像，所以答案是 true。 The left subtree 2(3,4) and right subtree 2(4,3) mirror each other, so the answer is true.

名詞解釋 / Glossary

• 二元樹 / Binary tree：每個節點最多有兩個子節點的樹狀結構，分別叫「左子節點」和「右子節點」。/ A tree where each node has at most two children, called the left child and right child.
• 節點 / Node：樹裡的一個元素，包含一個數值 val，以及指向左右子節點的指標 left、right。/ An element of the tree holding a value val and pointers left, right to its children.
• 指標 / Pointer（C/C++）：一個變數，裡面存的是「另一個東西的記憶體位址」。NULL（C）或 nullptr（C++）表示「沒有指向任何節點」，常用來代表空的位置。/ A variable holding the memory address of something else; NULL/nullptr means "points to nothing," used here for an empty spot.
• 鏡像對稱 / Mirror symmetry：把樹左右翻轉後和原本一模一樣。判斷方式是：一棵子樹的「左」要對上另一棵子樹的「右」。/ The tree equals its left-right flip. To check it, one subtree's left is compared with the other subtree's right.
• 遞迴 / Recursion：一個函式呼叫它自己來解決更小的相同問題，直到遇到最簡單的「終止條件」為止。/ A function calling itself on smaller versions of the same problem until a simple base case.
• 深度優先搜尋 (DFS) / Depth-First Search：沿著一條路走到底再回頭的走訪方式；遞迴天然就是 DFS。/ A traversal that goes as deep as possible before backing up; recursion is naturally DFS.
• 佇列 / Queue：一種「先進先出 (FIFO)」的容器，用來做迭代版的走訪。/ A first-in-first-out container, used for the iterative version.

思路

最直覺的想法可能是：把整棵樹的左半邊複製出來、翻轉、再和右半邊逐一比對。但這樣要額外建一棵樹，既浪費空間又麻煩。其實我們不需要真的翻轉，只要換個角度看「對稱」的定義：一棵樹對稱，等價於「它的左子樹」和「它的右子樹」互為鏡像。而兩棵樹互為鏡像的條件可以遞迴地拆解——根節點的值要相等，而且「A 的左」要對上「B 的右」、「A 的右」要對上「B 的左」。這就是關鍵不變式：比較時永遠是「外側對外側、內側對內側」。我們寫一個輔助函式 isMirror(a, b)，先處理最簡單的情況：兩個都是空 → 是鏡像（回傳 true）；只有一個是空 → 不是鏡像（回傳 false）；值不相等 → 不是鏡像。剩下的就交給遞迴：a->left 配 b->right，且 a->right 配 b->left，兩邊都要成立。這是深度優先的遞迴解。若不想用遞迴，也可以用一個佇列，每次成對地取出兩個節點來比較，並且成對地把它們的孩子「外、內」順序放進佇列，效果完全一樣。

The brute-force instinct might be to copy the left half, flip it, and compare it to the right half — but that builds an extra tree and wastes space. We don't actually need to flip anything if we reframe what "symmetric" means: a tree is symmetric exactly when its left subtree and its right subtree are mirror images of each other. "Two trees are mirrors" then decomposes recursively — their roots must have equal values, and A's left must match B's right while A's right matches B's left. That is the key invariant: we always pair outer-with-outer and inner-with-inner. We write a helper isMirror(a, b) handling the easy cases first: both null → mirror (true); exactly one null → not a mirror (false); different values → not a mirror. Otherwise recurse: a->left with b->right and a->right with b->left, both must hold. That's the depth-first recursive solution. If you prefer no recursion, use a queue: pull two nodes at a time to compare, and push their children in the outer/inner pairing — same logic, iterative form.

逐步走查 / Walkthrough

我們追蹤 root = [1,2,2,3,4,4,3] 的遞迴呼叫。一開始呼叫 isMirror(root->left, root->right)，也就是 isMirror(2, 2)（左邊的 2 和右邊的 2）。 We trace the recursive calls for root = [1,2,2,3,4,4,3]. It starts with isMirror(root->left, root->right) = isMirror(2, 2).

用 L 代表第一個參數（來自左半邊），R 代表第二個參數（來自右半邊）： Let L = first argument (from the left half), R = second argument (from the right half):

每一層的兩個子呼叫都回傳 true，用 && 往上合併，最後最外層 isMirror(2, 2) 回傳 true，整棵樹判定為對稱。 Every level's two sub-calls return true, combined upward with &&, so the outer isMirror(2, 2) returns true — the tree is symmetric.

注意第 2 步和第 5 步的配對：(3,3) 是「外側對外側」，(4,4) 是「內側對內側」。如果換成 [1,2,2,null,3,null,3]，第一層會變成 isMirror(2, 2)，接著配對 (NULL, 3) —— 一個空一個非空 —— 直接回傳 false。 Note the pairing in steps 2 and 5: (3,3) is outer-with-outer, (4,4) is inner-with-inner. For [1,2,2,null,3,null,3], the first level is still isMirror(2, 2), but a later pair becomes (NULL, 3) — one null, one not — returning false immediately.

Solution — C

/*
 * 演算法 / Algorithm:
 * 一棵樹對稱 ⇔ 左子樹與右子樹互為鏡像。
 * A tree is symmetric iff its left and right subtrees mirror each other.
 * 遞迴比較：兩邊的值相等，且「A左對B右、A右對B左」。
 * Recurse: values equal, and A.left~B.right and A.right~B.left.
 */

// LeetCode 已定義好這個結構，這裡列出方便理解 / LeetCode predefines this struct; shown for clarity:
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

#include <stdbool.h>  // 讓我們可以用 bool / true / false / gives us bool, true, false

// 輔助函式：判斷 a 和 b 兩棵子樹是否互為鏡像
// Helper: are subtrees a and b mirror images of each other?
static bool isMirror(struct TreeNode* a, struct TreeNode* b) {
    // 情況一：兩個都是空節點 → 它們對稱 / Case 1: both empty → they mirror.
    if (a == NULL && b == NULL) return true;
    // 情況二：只有一個是空 → 結構不對稱 / Case 2: exactly one empty → not symmetric.
    // (a==NULL || b==NULL) 能走到這裡代表「不是兩個都空」，所以只要有一個空就回傳 false
    // Reaching here means "not both null"; if either is null, they can't match.
    if (a == NULL || b == NULL) return false;
    // 情況三：兩個都非空，比較數值；不等就不對稱 / Case 3: both non-null; values must match.
    if (a->val != b->val) return false;
    // 遞迴：外側(a左,b右) 且 內側(a右,b左) 都要是鏡像
    // Recurse: outer pair (a.left,b.right) AND inner pair (a.right,b.left) must both mirror.
    // && 是「而且」：只有兩邊都 true，整體才 true / && means both must hold.
    return isMirror(a->left, b->right) && isMirror(a->right, b->left);
}

bool isSymmetric(struct TreeNode* root) {
    // 空樹視為對稱 / An empty tree is symmetric.
    if (root == NULL) return true;
    // 把「整棵樹是否對稱」轉化為「左子樹與右子樹是否互為鏡像」
    // Reduce "is the whole tree symmetric" to "do left and right subtrees mirror?"
    return isMirror(root->left, root->right);
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 一棵樹對稱 ⇔ 左子樹與右子樹互為鏡像。遞迴比較：
 * A tree is symmetric iff left and right subtrees mirror each other. Recurse:
 * 值相等，且 A.left~B.right、A.right~B.left。
 * values equal, and A.left~B.right and A.right~B.left.
 */

// LeetCode 已定義 TreeNode / LeetCode predefines TreeNode:
// struct TreeNode { int val; TreeNode *left; TreeNode *right; };

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 空樹視為對稱 / An empty tree is symmetric.
        if (root == nullptr) return true;
        // 轉化為兩棵子樹是否互為鏡像 / Reduce to: do the two subtrees mirror?
        return isMirror(root->left, root->right);
    }

private:
    // 輔助函式：a 與 b 是否互為鏡像 / Helper: do a and b mirror each other?
    bool isMirror(TreeNode* a, TreeNode* b) {
        // 兩個都空 → 對稱 / Both empty → mirror.
        if (a == nullptr && b == nullptr) return true;
        // 只有一個空 → 不對稱 / Exactly one empty → not a mirror.
        if (a == nullptr || b == nullptr) return false;
        // 值不同 → 不對稱 / Different values → not a mirror.
        if (a->val != b->val) return false;
        // 外側配外側、內側配內側，兩者皆須成立
        // Outer with outer, inner with inner; both must hold.
        return isMirror(a->left, b->right) && isMirror(a->right, b->left);
    }
};

複雜度 / Complexity

• Time: O(n) — n 是節點總數。每個節點最多被 isMirror 造訪並比較一次，所以總時間跟節點數成正比。/ n is the number of nodes; each node is visited and compared at most once, so time grows linearly with node count.
• Space: O(h) — h 是樹的高度，來自遞迴呼叫堆疊 (call stack)。最壞情況樹退化成一條鏈時 h = n，變成 O(n)；平衡樹則約為 O(log n)。/ h is the tree height, from the recursion call stack; worst case (a chain) is O(n), a balanced tree is about O(log n).

Pitfalls & Edge Cases

• 只比較左右子樹的值，不比結構 / Comparing values but ignoring structure：如果忘了「一個空一個非空」這個檢查，[1,2,2,null,3,null,3] 會被誤判成對稱。程式碼用第二個 if (a==NULL || b==NULL) return false; 專門擋這種情況。/ Forgetting the "one null, one not" check would wrongly accept [1,2,2,null,3,null,3]; the second if guards it.
• 配對方向搞反 / Wrong pairing direction：對稱必須是 a->left 配 b->right（外對外），不是 a->left 配 b->left。若配成同側，等於在比「兩棵一樣的樹」而不是「鏡像」，會得到錯誤答案。/ Symmetry pairs a->left with b->right, not same-side; pairing same-side checks equality, not mirroring.
• 空樹 / Empty root：題目保證至少 1 個節點，但保留 root == NULL → true 讓程式更健壯。/ Constraints guarantee ≥1 node, but handling root == nullptr keeps the code robust.
• 判空順序 / Order of null checks：一定要先寫「兩個都空 → true」，再寫「其中一個空 → false」。順序寫反的話，兩個都空時會錯誤地回傳 false。/ Check "both null → true" before "one null → false"; reversing the order returns false when both are null.
• 值相等別用位址比較 / Compare values, not pointers：要寫 a->val != b->val，而不是 a != b。後者比的是記憶體位址，兩個不同節點永遠不相等。/ Use a->val != b->val, not a != b; the latter compares addresses and two distinct nodes never match.