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

題目描述

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

遞歸解法（標準解）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 兩棵樹均為空 → 相同
        if (p == null && q == null) return true;
        // 一棵為空、一棵不為空 → 不同
        if (p == null || q == null) return false;
        // 當前節點值不同 → 不同
        if (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/DFS 显式堆疊）

避免遞歸堆疊溢出風險，適合極深樹。

public boolean isSameTree(TreeNode p, TreeNode q) {
    Deque stack = new ArrayDeque<>();
    stack.push(new TreeNode[]{p, q});
    while (!stack.isEmpty()) {
        TreeNode[] nodes = stack.pop();
        TreeNode n1 = nodes[0], n2 = nodes[1];
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        stack.push(new TreeNode[]{n1.right, n2.right});
        stack.push(new TreeNode[]{n1.left, n2.left});
    }
    return true;
}

核心考點總結

1. **空節點處理** 是遞歸終止條件關鍵，須優先判斷。
2. **值比較** 在非空前提下進行。
3. **結構同步遍歷**：左子樹對左子樹、右子樹對右子樹，不可交叉。
4. **迭代寫法** 展示對資料結構掌握度，面試常被要求補充。