LeetCode 572. 另一棵树的子树
目录
题目描述
题意分析
给两棵二叉树
root和subRoot，问subRoot是不是root的一棵子树，返回布尔值。关键在题目对「子树」的定义：从
root里挑一个节点，连同这个节点在root中的全部后代一起取出来，得到的那棵树必须与subRoot结构和取值完全一致。「全部后代」四个字是全题的分水岭——不允许只对上一部分就算数，root里那个节点下面多长出任何一个叶子，匹配就作废。同时它也说明子树只能整块地取，不能跳过中间层去拼凑。由此推出的判定标准是双向的：
subRoot有的节点root对应位置必须有且值相等，root对应位置有的节点subRoot也必须有。空的位置也要对上，左右孩子的空缺同样是结构的一部分，[1,2]和[1,null,2]不算相同。约束上两棵树的节点数都不超过 2000，值域是 $[-10^4, 10^4]$，规模很小，$O(mn)$ 的朴素做法完全能过，所以本题考的是判定逻辑写不写得干净，而不是能不能优化。
边界要留意：
subRoot题目保证非空，但递归途中一定会出现「一边空、另一边非空」以及「两边都空」的组合，必须分开处理；root走到空时不可能再容纳非空的subRoot；两棵树里可以有大量重复值，所以值相等绝不能当作匹配成功的依据。
解法：枚举起点并比较整棵子树
核心思路
问题关键：
subRoot可能从root的任意节点开始，且匹配后必须包含该节点的全部后代。问题因此分成「寻找候选起点」和「验证两棵树完全相同」两层。为什么选双递归：外层
isSubtree枚举root的每个节点；内层same从当前候选开始同步比较两棵树。题目节点数不超过 2000，最坏 $O(mn)$ 的直接解法足够，也比序列化、树哈希更容易正确实现和讲解。状态与不变量：外层始终保持目标
subRoot不变，只移动候选根；内层的same(a, b)当且仅当两棵子树结构完全一致且对应节点值相等。内层要求「两边同时为空才成功、一边为空就失败」，空孩子也是树结构的一部分。正确性：外层会访问
root的每个节点，因此不会漏掉可能的子树根。对每个候选，内层递归检查根值、左子树和右子树；三者都成立才返回true，所以不会把只匹配前缀或部分后代的结构误判为子树。外层是「存在一个候选」所以用或，内层是「所有对应位置都一致」所以用与。这也是本题最值得在面试中主动说明的逻辑分工。
解题步骤
- 外层若
root为空，只能与空目标匹配。- 先调用
same(root, subRoot)，尝试把当前节点作为候选起点。- 当前候选失败时，继续在
root.left和root.right中寻找，目标树保持不变。same中若两节点同时为空，返回true；若只有一个为空或值不同，返回false。- 当前值相等时，递归要求左对左、右对右都完全相同。
口述样例：
root = [3,4,5,1,2]、subRoot = [4,1,2]。候选3因根值不同失败；移动到节点4后，根值以及左右子树都匹配，返回true。若原树的节点2下面额外多一个0，比较到0/null时失败，说明「多出的后代」同样会破坏子树匹配。
代码实现
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null) {
return subRoot == null;
}
return same(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
private boolean same(TreeNode first, TreeNode second) {
if (first == null && second == null) {
return true;
}
if (first == null || second == null || first.val != second.val) {
return false;
}
// 子树匹配要求左右结构和值都完全一致。
return same(first.left, second.left) && same(first.right, second.right);
}
}
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
if root == nil {
return subRoot == nil
}
return sameTree(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot)
}
func sameTree(first *TreeNode, second *TreeNode) bool {
if first == nil && second == nil {
return true
}
if first == nil || second == nil || first.Val != second.Val {
return false
}
// 必须从当前节点开始整棵树完全一致。
return sameTree(first.Left, second.Left) && sameTree(first.Right, second.Right)
}
复杂度分析
- 时间复杂度：最坏 $O(mn)$。外层最多枚举
m个候选，每次内层最多比较n个节点。- 空间复杂度：$O(h_1 + h_2)$，来自两层递归栈；退化树下最坏为 $O(m+n)$。
关键点总结
- 外层枚举候选起点，内层验证整棵树；两层职责和参数移动方式不能混淆。
- 外层用或表示「存在」，内层用与表示「全部匹配」。
- 两边同时为空才表示结构对齐；一边为空说明结构不同。
- 100 题只有严格相等判断；剑指 Offer 26 的「子结构」允许目标树先结束，本题不允许。
- 若数据规模更大，可把含空节点标记的前序序列化转为字符串匹配，或使用树哈希；本题约束下没有必要增加复杂度。
易错点总结
- 把
second == null直接视为成功，会把「子树」误写成「子结构」；root = [4,1,2]、subRoot = [4]应为false。- 把两边同时为空也判成失败：两个单节点树将无法匹配。
- 外层递归时同步移动
subRoot，会不断削短目标树；外层只应改变候选节点。- 只比较根值，不继续验证左右结构；重复值场景会产生大量误判。
- 序列化优化若不补空节点占位符和数值分隔符，会丢失结构或混淆
1与12等节点边界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 100. 相同的树 | 简单 | 本题的内层函数单独成题，两棵树从根对齐一次比到底，无需枚举起点 |
| 剑指 Offer 26. 树的子结构 | 中等 | 同为外层枚举起点，但内层放松：B 走到空即算匹配，且空树不是子结构 |
| 面试题 04.10. 检查子树 | 中等 | 与本题判定完全一致，可追加序列化加 KMP 的 $O(m+n)$ 解法 |
| 101. 对称二叉树 | 简单 | 同样是双指针同步递归，但比较方向交叉为左对右、右对左 |
| 652. 寻找重复的子树 | 中等 | 从「判一次」升级为「找全部重复」，需用序列化加哈希表把两两比较降到一遍遍历 |
| 1367. 二叉树中的链表 | 中等 | 目标从树换成链，内层沿单条路径向下匹配，链走完即成功 |