LeetCode 判斷兩棵二叉樹是否相同：遞歸與迭代雙解法

題目描述

給定兩棵二叉樹的根節點 p 和 q，判斷它們是否完全相同。相同定義為：結構相同，且對應節點值相等。

遞歸解法（最直觀）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 都為空 → 相同
    if (!p && !q) return true;
    // 一空一不空 → 不同
    if (!p || !q) return false;
    // 值不同 → 不同
    if (p->val != q->val) return false;
    // 遞歸比較左右子樹
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

遞歸過程圖解

    p:     1          q:     1
         / \                / \
        2   3              2   3

比較流程：
1. 根 1==1 ✅
2. 左子樹 2==2 ✅ → 兩側均為葉子，返回 true
3. 右子樹 3==3 ✅ → 兩側均為葉子，返回 true
4. 總體 true

迭代解法（BFS/DFS，避免棧溢出）

BFS 隊列法

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;
}

DFS 棧法

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

複雜度分析

進階：結構相同但值可不同？

若只判斷結構同構（忽略值），將 n1->val != n2->val 條件移除即可。

相關經典題

• LeetCode 572 另一棵樹的子樹（子樹匹配）
• LeetCode 100 相同的樹（本題）
• LeetCode 101 對稱二叉樹（鏡像對比）
• LeetCode 965 單值二叉樹（所有節點值相同）

總結

• 遞歸代碼最短、可讀性最強，面試首選
• 深度極大樹（>10⁴）需用迭代避免棧溢出
• 核心邏輯：同步遍歷兩棵樹，任意節點不匹配即返回 false