LeetCode Same Tree：遞歸判斷兩棵二叉樹完全相同

題目回顧

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

遞歸解法

class Solution {
public:
    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/DFS）

bool isSameTree(TreeNode* p, TreeNode* q) {
    queue> que;
    que.emplace(p, q);
    while (!que.empty()) {
        auto [n1, n2] = que.front(); que.pop();
        if (!n1 && !n2) continue;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;
        que.emplace(n1->left, n2->left);
        que.emplace(n1->right, n2->right);
    }
    return true;
}

複雜度

• 時間：O(min(n,m))，n,m 為兩樹節點數
• 空間：遞歸 O(h)，迭代 O(w) 寬度

總結

樹的遞歸判斷模板：空檢查 → 值比較 → 遞歸左右。同理可解對稱樹、子樹判斷等變體。