LeetCode Same Tree（判斷兩棵二叉樹是否相同）

LeetCode Same Tree（判斷兩棵二叉樹是否相同）

題目連結： LeetCode 100. Same Tree

題意

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

遞歸解法

遞歸終止條件：

• 兩節點皆為空 → 相同，返回 true。
• 一空一不空 → 不同，返回 false。
• 值不相等 → 不同，返回 false。

遞歸步驟：同時遞歸檢查左子樹與右子樹，邏輯與（&&）。

Java 實現

/**
 * 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);
    }
}

迭代解法（BFS/DFS）

也可用隊列或棧模擬遞歸，同步遍歷兩棵樹，逐節點比較。

public boolean isSameTree(TreeNode p, TreeNode q) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(p);
    queue.offer(q);
    while (!queue.isEmpty()) {
        TreeNode n1 = queue.poll();
        TreeNode n2 = queue.poll();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null) return false;
        if (n1.val != n2.val) return false;
        queue.offer(n1.left);
        queue.offer(n2.left);
        queue.offer(n1.right);
        queue.offer(n2.right);
    }
    return true;
}

複雜度分析

• 時間：O(min(N, M))，N, M 為兩樹節點數，最壞情況遍歷較小樹所有節點。
• 空間：遞歸 O(H)（樹高），迭代 O(W)（最大寬度）。