LeetCode Symmetric Tree：遞歸與迭代判斷對稱二叉樹

問題描述

給定二叉樹根節點，判斷是否鏡像對稱（即左右子樹互為鏡像）。

方法一：遞歸

定義輔助函數 check(left, right)：

• 兩空 → true。
• 一空 → false。
• 值不等 → false。
• 遞歸檢查 left.left vs right.right 且 left.right vs right.left。

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    function check = [&](TreeNode* L, TreeNode* R) {
        if (!L && !R) return true;
        if (!L || !R) return false;
        return L->val == R->val && check(L->left, R->right) && check(L->right, R->left);
    };
    return check(root->left, root->right);
}

方法二：迭代（雙棧/隊列）

同時遍歷左右子樹，順序互為鏡像。用棧或隊列存節點對。

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    stack stL, stR;
    stL.push(root->left); stR.push(root->right);
    while (!stL.empty() && !stR.empty()) {
        TreeNode* L = stL.top(); stL.pop();
        TreeNode* R = stR.top(); stR.pop();
        if (!L && !R) continue;
        if (!L || !R || L->val != R->val) return false;
        stL.push(L->left); stL.push(L->right);
        stR.push(R->right); stR.push(R->left); // 順序相反
    }
    return true;
}

方法三：中序遍歷檢查回文（不推薦）

中序遍歷得到序列，檢查是否回文。但不同結構樹可能中序相同，故不可靠，除非同時記錄結構（如加入 null 標記）。

複雜度

• 時間 O(n)，每個節點訪問常數次。
• 空間 O(h) 遞歸棧 / 顯式棧，最壞 O(n)。

總結

對稱樹判斷核心在於「左右子樹互為鏡像」的遞歸定義。遞歸代碼最簡潔，迭代版本考察對遍歷順序的控制。兩種寫法都應熟練掌握。