LeetCode 100. 相同的树
目录
题目描述
题意分析
输入两棵二叉树的根节点，输出一个布尔值：两棵树是否「相同」。题面对相同的定义有两层，缺一不可——形状要一样（每个位置上有节点或没节点必须对得上），并且对应位置上的节点值也要一样。
约束里有两个信号。一是节点数量最多 $100$，说明树很小，递归深度即使退化成链也不会爆栈，不必为了迭代而迭代；二是节点值可以是负数（范围 $[-10^4, 10^4]$），所以不能拿
0、-1这类值当「空节点」的哨兵，判空只能老老实实判引用。边界情况有三种要想清楚：两棵树都是空树时答案为真；一棵空、一棵非空时答案为假；两棵树节点数相同但形状不同（比如一棵是「根带左孩子」、另一棵是「根带右孩子」）时答案也为假。最后这种最容易被漏掉，它决定了不能只比较节点值的集合或某种不带位置信息的序列。
解法：递归同步比较
核心思路
两棵树相同，要求每个对应位置同时满足「是否为空一致」和「节点值一致」。因此让两个指针同步向下比较，比先生成遍历序列更直接；普通中序遍历不记录空节点，无法唯一表示树的结构。
递归契约是：
isSameTree(p, q)判断以p、q为根的两棵子树是否完全相同。若两者都为空则相同；只有一个为空则结构不同；两者都非空时，必须当前值相等，并且左子树对左子树、右子树对右子树都相同。正确性可由树高归纳得到：空树情形由终止条件正确判断；对于非空树，根节点和值由当前层判断，左右子树由递归契约判断。三部分都成立时整棵树相同，任一部分不成立都会短路返回
false。
解题步骤
- 若至少一个节点为空，直接返回
p == q：同时为空为真，只有一个为空为假。- 此时两个节点都非空，先比较节点值；不同则立即返回
false。- 递归比较
p.left与q.left，再比较p.right与q.right。- 只有当前值和两对子树都相同，当前两棵子树才相同。
例如
p = [1,2,3]、q = [1,2,4]：根和左子树相同，比较右子树时发现3 != 4，结果为false。若某个对应位置只有一边为空，也会在判空处立即识别出结构不同。
代码实现
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);
}
}
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil || q == nil {
return p == q
}
return p.Val == q.Val &&
isSameTree(p.Left, q.Left) &&
isSameTree(p.Right, q.Right)
}
复杂度分析
- 时间复杂度：$O(\min(m, n))$，其中 $m$、$n$ 是两棵树的节点数；每对对应节点最多比较一次，遇到差异会提前结束。两棵树完全相同时可写为 $O(n)$。
- 空间复杂度：$O(h)$，其中 $h$ 是共同遍历部分的最大深度；最坏为 $O(n)$，平衡树为 $O(\log n)$。
关键点总结
- 结构和值必须同时相同，判空要先于访问节点值。
- 两棵树同步递归，参数天然表示一对对应位置，不需要额外存路径。
- 左对左、右对右；若改成左对右、右对左，判断的是镜像而不是相同。
&&的短路求值能在发现首个差异后停止无效遍历。
易错点总结
- 在判空前访问
val会产生空指针异常。- 写成
if (p == null || q == null) return false会把两棵空树误判为不同，应返回p == q。- 只比较遍历值序列会丢失空节点位置，不足以判断树的结构。
- 递归时交叉比较左右孩子判断的是镜像关系，不是相同关系。
- 当前节点值相等不能直接返回
true，左右子树仍可能在结构或值上不同。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 101. 对称二叉树 | 简单 | 镜像方向同步比较 |
| 226. 翻转二叉树 | 简单 | 单树左右子树交换 |
| 572. 另一棵树的子树 | 简单 | 逐节点尝试匹配 |
| 617. 合并二叉树 | 简单 | 双树同步遍历建新树 |
| 951. 翻转等价二叉树 | 中等 | 允许翻转的等价判定 |
| 652. 寻找重复的子树 | 中等 | 子树序列化去重 |
| 剑指 Offer 26. 树的子结构 | 中等 | 子结构包含判定 |