LeetCode Same Tree：遞歸與迭代雙法判斷二叉樹相同

問題描述

判斷兩棵二叉樹是否完全相同（結構相同且對應節點值相同）。

遞歸法

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val
        && isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

迭代法（雙隊列 BFS）

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    queue q1, q2;
    q1.push(p); q2.push(q);
    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->left) { q1.push(a->left); q2.push(b->left); }
        else if (a->left || b->left) return false;
        if (a->right && b->right) { q1.push(a->right); q2.push(b->right); }
        else if (a->right || b->right) return false;
    }
    return true;
}

複雜度

• 時間：O(n)
• 空間：O(n) 隊列/棧