LeetCode Same Tree：判斷兩棵二叉樹是否完全相同

問題描述

給定兩棵二叉樹的根節點 p 和 q，編寫函數判斷它們是否「相同」。兩棵樹相同的定義是：結構完全一致，且對應節點的值相等。

遞歸解法

這是一道經典的樹遞歸題。基本思路：

1. 若兩節點皆為空，返回 true。
2. 若一空一不空，或值不等，返回 false。
3. 否則遞歸比較左子樹與右子樹，皆相同才返回 true。

C++ 實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q || p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

複雜度分析

• 時間：\( O(\min(N, M)) \)，N、M 為兩樹節點數。最壞情況遍歷較小樹的所有節點。
• 空間：\( O(H) \)，H 為樹高（遞歸棧深度）。最壞退化為鏈表時 \( O(N) \)，平衡樹時 \( O(\log N) \)。

迭代寫法（BFS）

也可用隊列層序遍歷同步比較，避免遞歸棧溢出：

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

總結

Same Tree 考察對二叉樹遞歸結構的理解。遞歸寫法簡潔直觀，迭代寫法更適合深度極大的樹。掌握兩種寫法可靈活應對面試與工程場景。