572. 另一棵树的子树（Subtree of Another Tree）
难度：简单 | 主题：二叉树、DFS、递归
题目
给你两棵二叉树 root 和 subRoot。判断 root 中是否包含一棵和 subRoot 结构相同、节点值相同的子树。如果存在，返回 true；否则返回 false。
示例
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
解释：root 中以 4 为根的子树和 subRoot 完全一致
思路
先讲个故事：拼图里找碎片
想象你有一幅巨大的拼图（root），手里拿着一个小碎片（subRoot）。
你要判断：这个碎片是不是大拼图中完整的一块？
这需要两步：
-
在大拼图里找到一个起点，看起来和小碎片的图案可能匹配
-
从这个起点出发，逐块比较，确认每一块都对得上
对应到树上也是两步：遍历找候选根 + 递归比较是否相同。
引导式推导：从单点到双递归
第 1 步：怎么判断两棵树完全相同？
100相同的树 告诉我们：
check(o, t)：
都空 → True
一空一不空 / 值不同 → False
递归比较左右子树
第 2 步：怎么找候选根？
对 root 的每个节点，都问一句：“以你为根的子树和 subRoot 一样吗？”
isSubtree(root, subRoot)：
root 为空 → False（没地方找了）
root 和 subRoot 相同？→ True（找到了！）
在左子树里找 → isSubtree(root.left, subRoot)
在右子树里找 → isSubtree(root.right, subRoot)
第 3 步：双递归的嵌套
这就是经典的双递归模式：
-
外层递归（
isSubtree）：在大树上遍历每个节点 -
内层递归（
check/isSameTree）：在固定节点上比较两棵树
外层：找起点 内层：逐点校验
┌─────────────┐ ┌────────────────────┐
│ 遍历每个节点 │──候选根──→│ 比较两棵树是否相同 │
│ isSubtree │ │ check(sameTree) │
└─────────────┘ └────────────────────┘
代码
def isSubtree(self, s, t):
# s: 大树，t: 子树模板
# 遍历 s 的每个节点，尝试匹配 t
if not s: # 大树遍历到空了还没找到
return False
# 三路或：当前节点匹配 OR 左子树里有 OR 右子树里有
return (self.check(s, t) or
self.isSubtree(s.left, t) or
self.isSubtree(s.right, t))
def check(self, o, t):
# 逐节点比较两棵树是否完全相同
if not o and not t: # 同时遍历完 → 完全匹配
return True
if not o or not t or o.val != t.val: # 结构不同或值不同 → 不匹配
return False
# 左右子树必须同时完全相同
return self.check(o.left, t.left) and self.check(o.right, t.right)
为什么三路用 or？
只要有一条路找到就行。找到 → 直接返回 True，不用继续找了。
如果当前节点不匹配，往左子树找 OR 往右子树找，两个方向有一个成功就行。
复杂度
| 解法 | 时间 | 空间 |
|---|---|---|
| DFS 遍历 + 比较 | O( | s |
| 序列化 + KMP（进阶） | O( | s |
最坏情况：每个 s 节点都要和 t 完整比较一次（比如 s 全是相同值的节点，t 是单节点树），复杂度退化为 O(n×m)。
实战考量
频率分析
出现在：字节/美团 二叉树递归考察题，实践中频。考察对递归嵌套的理解，比单纯遍历多一层抽象。
延伸思考
Q：为什么不用写 isSubtree(s, t) 的边界条件是 if not s and not t: return True？
A：题目保证 t 非空。s 为空 t 非空 → 不是子树，返回 False。且 t 如果是空树（题目不会给），按定义任何树都有空子树，应该返回 True。但本题约定 t 非空。
Q：序列化 + KMP 的思路是什么？
A：把两棵树序列化成字符串（前序/后序，用特殊标记表示空节点），问题转化为”subRoot 的序列是否是 root 序列的子串”。KMP O(n+m) 匹配。提出来可以加分，但手写递归足够。
Q：外层递归的最坏复杂度？
A：每个 s 节点都可能触发一次完整的 check。如果 s 退化成链表且每个节点值都等于 t 的根值，那么每个节点都要和 t 完整比较，O(n×m)。
Q：如果 root 中有多个匹配呢？
A：找到一个就返回 True，不会继续找。这是三路 or 的短路特性。
易错点
-
外层
or逻辑：不能写成and——三路是”有一条路通就行” -
check的空判断：先判断同时空（True），再判断一空一不空（False）。顺序不能反，否则if not o and not t先被not o or not t拦截了 -
isSubtree的空处理：if not s: return False——s 空了但 t 非空，不是子树 -
值和结构都要比较，只比较结构（101对称二叉树）或只比较值都不够
生活类比
找子树 → 在拼图里找完整碎片
你有一块小碎片（subRoot），要在大拼图（root）里找。
外层循环（isSubtree）是”扫描——这里看起来像起点吗？”
内层比较（check）是”逐一比对——这块对齐吗？下一块呢？”
两件事都得做：不扫描找不到起点，不比对比不知道是不是真的一样。
相关题目
| 题目 | 关系 |
|---|---|
| 100相同的树 | check 函数的来源，完全相同的问题 |
| 104二叉树的最大深度 | 二叉树递归遍历基础 |
| 543二叉树的直径 | 同是后序 DFS 遍历框架 |
| 101对称二叉树 | 比较两棵树的对称版本 |
→ 返回题单：LeetCode学习路线图 > 五、二叉树
速记卡（面试闪卡）
Q1：一句话讲清「572. 另一棵树的子树（Subtree of Another Tree）」到底是什么？
A：判子树用双递归：外层遍历找候选根，内层逐点比两树是否相同。
Q2：一、题目与拼图碎片类比 —— 怎么理解？
A：像在大拼图里找完整小碎片：先在大图里找一个”看起来像起点”的位置，再从这出发逐块比对，两步缺一不可。英文：Subtree Matching。
Q3：二、双递归：isSubtree 套 check —— 怎么理解？
A：像两层排查：外层 isSubtree 遍历大树每个节点当候选根，内层 check 固定起点逐点比两棵树——典型的”遍历+校验”嵌套。英文：Double Recursion。
Q4：三、为什么三路用 or —— 怎么理解？
A：像三条路只要一条通：当前节点匹配、或左子树里有、或右子树里有，任一为真即返回 True，利用短路早停——写成 and 就错了。英文：OR Short-circuit。
Q5：四、复杂度与进阶 KMP —— 怎么理解？
A：像最坏每点都比一遍：时间 O(|s|×|t|)、空间 O(深度)；进阶把两树序列化再 KMP 子串匹配可降到 O(|s|+|t|)，加分但不必手写。英文：DFS / Serialize+KMP。
Q6：核心速记主线有哪些？
-
双递归：外层 isSubtree 遍历、内层 check 比同树
-
三路 or：当前 / 左 / 右任一匹配即 True
-
复杂度：时间 O(|s|×|t|)、空间 O(最大深度)
-
进阶：序列化+KMP 可优化到 O(|s|+|t|)
口诀
A：子树拼图慢慢认，
外层找根内层问；
三路或通便为真，
双递归嵌套稳。