LeetCode 100：相同的樹 — 遞歸、DFS 棧、BFS 隊列三種寫法

題目描述

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

解法一：遞歸（最直觀）

bool isSameTree(TreeNode* p, 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);
}

解法二：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->left, n2->left);
        st.emplace(n1->right, n2->right);
    }
    return true;
}

解法三：BFS + 隊列

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

複雜度分析

• 時間：O(n) —— 遍歷所有節點。
• 空間：遞歸 O(h)，棧/隊列 O(w)（w 為最大寬度），最壞 O(n)。