LeetCode Symmetric Tree：遞歸與迭代雙解法判斷二叉樹鏡像對稱

題目描述

給定一棵二叉樹，判斷其是否鏡像對稱（即左右子樹結構與數值完全鏡像）。

    1         1
   / \       / \
  2   2     2   2
 / \ / \   \   \
3  4 4  3   3   3
對稱        不對稱

遞歸解法（最直觀）

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}

bool isMirror(TreeNode* L, TreeNode* R) {
    if (!L && !R) return true;
    if (!L || !R) return false;
    return (L->val == R->val) 
        && isMirror(L->left,  R->right)
        && isMirror(L->right, R->left);
}

核心思想：雙指針同步遍歷，左樹的左 ↔ 右樹的右，左樹的右 ↔ 右樹的左。

迭代解法（BFS 雙隊列）

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    queue q1, q2;
    q1.push(root->left);
    q2.push(root->right);
    while (!q1.empty() && !q2.empty()) {
        TreeNode* n1 = q1.front(); q1.pop();
        TreeNode* n2 = q2.front(); q2.pop();
        if (!n1 && !n2) continue;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;
        q1.push(n1->left);  q1.push(n1->right);
        q2.push(n2->right); q2.push(n2->left);  // 注意順序相反
    }
    return true;
}

複雜度

• 時間：O(n)，每個節點訪問一次
• 空間：遞歸 O(h)（棧深度），迭代 O(w)（隊列寬度），最壞 O(n)

擴展：Follow-up

若樹節點值範圍大、需序列化比較，可先序列化為字符串（含 null 佔位），再判斷字符串是否回文。