树与图简单2 种解法

#100相同的树

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

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

解题主线

每次必须成对比较同一位置的节点。

结构不同与节点值不同都应立即失败。

解法 1：递归同步比较

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

时间复杂度

O(n)

空间复杂度

O(h)

100. 相同的树 · 递归同步比较

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 为最大层宽

100. 相同的树 · 广度优先成对比较

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<>();
        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