树与图简单2 种解法

#100相同的树

判断两棵二叉树的结构和对应节点值是否完全相同。

#二叉树#深度优先搜索#广度优先搜索

原题

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-10⁴ <= Node.val <= 10⁴

查看原题

解题主线

每次必须成对比较同一位置的节点。
结构不同与节点值不同都应立即失败。

解法 1：递归同步比较

同步递归两棵树的左右子树。

时间复杂度： O(n)
空间复杂度： O(h)

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 同一位置只要有一个为空，必须两者都为空才保持结构一致
        if (p == null || q == null) return p == q;
        // 值相等后再同步比较左右对应子树，任一失败即可短路
        return p.val == q.val
                && isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right);
    }
}

解法 2：广度优先成对比较

队列中保存节点对，逐层检查结构和值。

时间复杂度： O(n)
空间复杂度： O(w)，w 为最大层宽

JAVA

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Deque<TreeNode[]> queue = new ArrayDeque<>();
        // 用非空数组包装节点对，使队列可表示其中一侧为 null 的结构差异
        queue.offer(new TreeNode[] {p, q});
        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode a = pair[0], b = pair[1];
            if (a == null || b == null) {
                // 同一位置只有一侧为空时，两棵树结构不同
                if (a != b) return false;
                continue;
            }
            if (a.val != b.val) return false;
            // 左右孩子始终按对应位置成对入队
            queue.offer(new TreeNode[] {a.left, b.left});
            queue.offer(new TreeNode[] {a.right, b.right});
        }
        return true;
    }
}

边界与易错点

队列实现不能直接向 ArrayDeque 放入 null，可将一对节点包装为非空数组。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q100_isSameTree.java