您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode Symmetric Tree：遞歸與迭代雙重實現判斷二叉樹鏡像對稱

編輯：關於C++

問題描述

判斷二叉樹是否鏡像對稱（即左子樹與右子樹鏡像）。

遞歸解法

輔助函數 isMirror(p, q) 判斷兩棵樹是否鏡像：

兩空 → true
一空 → false
值不同 → false
遞歸檢查 p.left ↔ q.right 且 p.right ↔ q.left


bool isSymmetric(TreeNode* root) {
    return isMirror(root, root);
}
bool isMirror(TreeNode* a, TreeNode* b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    return a->val == b->val
        && isMirror(a->left, b->right)
        && isMirror(a->right, b->left);
}

迭代解法（雙隊列 BFS）

兩隊列分別存儲待比較的鏡像節點對：


bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    queue q1, q2;
    q1.push(root); q2.push(root);
    while (!q1.empty()) {
        TreeNode* a = q1.front(); q1.pop();
        TreeNode* b = q2.front(); q2.pop();
        if (a->val != b->val) return false;
        if (a->left && b->right) { q1.push(a->left); q2.push(b->right); }
        else if (a->left || b->right) return false;
        if (a->right && b->left) { q1.push(a->right); q2.push(b->left); }
        else if (a->right || b->left) return false;
    }
    return true;
}