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

題目簡介

判斷二叉樹是否關於根節點鏡像對稱。即左子樹與右子樹互為鏡像。

解法一：遞歸

輔助函數 check(a, b) 判斷兩棵樹是否互為鏡像：

• 兩者皆空 → true。
• 一空一非空 → false。
• 值不等 → false。
• 遞歸檢查 check(a.left, b.right) && check(a.right, b.left)。

解法二：迭代（BFS 雙隊列）

用兩個隊列分別存左子樹和右子樹節點，每次取出一對比較，子節點按鏡像順序入隊：左樹的左/右 對應 右樹的右/左。

解法三：迭代（單隊列存配對）

隊列存 pair<TreeNode*, TreeNode*>，初始放 (root.left, root.right)，每次取出比較，按鏡像順序壓入子配對。

代碼實現

// 遞歸
bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    function<bool(TreeNode*,TreeNode*)> check = [&](TreeNode* a, TreeNode* b) {
        if (!a && !b) return true;
        if (!a || !b) return false;
        return a->val == b->val && check(a->left, b->right) && check(a->right, b->left);
    };
    return check(root->left, root->right);
}

// 迭代（單隊列）
bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    queue<pair<TreeNode*,TreeNode*>> q;
    q.emplace(root->left, root->right);
    while (!q.empty()) {
        auto [a, b] = q.front(); q.pop();
        if (!a && !b) continue;
        if (!a || !b) return false;
        if (a->val != b->val) return false;
        q.emplace(a->left, b->right);
        q.emplace(a->right, b->left);
    }
    return true;
}

複雜度分析

時間 O(n)，空間 O(n)（最壞情況隊列/遞歸棧存儲所有節點）。