教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读「另一棵树的子树」Subtree of Another Tree是 LeetCode 上一道经典的二叉树「树形同构判定」题目给定两棵二叉树root与subRoot判断subRoot是否为root的子树。该题同时出现在「算法面试 200 题」与「分类刷题清单」中见 docs/00_preface/00_06_categories_list.md 与 docs/00_preface/00_08_interview_200_list.md是面试中出现频率极高的递归入门题。读完本文你将掌握「树相等性判定」「子树包含判定」的递归分解方法理解 $O(m \times n)$ 复杂度的来源并学会序列化 字符串匹配KMP与子树哈希两种进阶优化思路。一、题目回顾什么是「另一棵树的子树」1.1 题目要求给定两棵二叉树的根节点root和subRoot要求检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在返回true否则返回false。这里对「子树」的定义非常严格来自 docs/05_tree/05_01_tree_basic.md 中树的递归定义一棵树的子树是该树中某个节点及其全部后代节点构成的树。也就是说subRoot必须与root中某一棵子树在结构上完全一致、对应节点值完全相同才算是匹配成功。1.2 示例解析示例 1输入root [3,4,5,1,2], subRoot [4,1,2] 输出trueroot中节点4及其后代1、2构成的结构与subRoot[4,1,2]完全相同因此返回true。示例 2输入root [3,4,5,1,2,null,null,null,null,0], subRoot [4,1,2] 输出false示例 2 与示例 1 仅差一处root的节点1多了一个值为0的左孩子。此时以节点4为根的子树变成了[4,1,2,null,0]结构与subRoot [4,1,2]不再一致因此返回false。这个对比直观地说明「子树」判定是「结构 值」的双重匹配只比较根节点值或只比较部分结构都是不够的。1.3 数据范围约束root树上节点数量范围[1, 2000]subRoot树上节点数量范围[1, 1000]节点值范围-10^4 ≤ root.val, subRoot.val ≤ 10^4约束决定了算法需要支持的最坏规模当root有 2000 个节点、subRoot有 1000 个节点时朴素递归的最坏比较次数约为 2000 × 1000 次量级仍然在可接受范围内这也是递归匹配能作为官方标准解的原因。二、核心概念铺垫树的相等性与子树2.1 二叉树的递归结构二叉树是一种递归定义的数据结构一个根节点 两棵互不相交的左、右子树左右子树本身也都是二叉树见 docs/05_tree/05_01_tree_basic.md。这一定义决定了凡是涉及「两棵树比较」的问题天然适合用递归分解到「比较根节点 递归比较左子树 递归比较右子树」。二叉树的链式存储节点定义如下同样来自 docs/05_tree/05_01_tree_basic.mdclass TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val # 节点的值 self.left left # 左子节点指针 self.right right # 右子节点指针2.2 「相同的树」是子问题的基础判断子树是否匹配本质上是在判断以root中某个节点为根的树与subRoot是否完全相同。而「两棵树完全相同」的判定正是 LeetCode 0100「相同的树」这一基础题题解见 docs/solutions/0100-0199/same-tree.md两棵树相同当且仅当两棵树的根节点值相等且它们的左子树相同、右子树相同。其递归判定可以写成def isSameTree(p, q): if not p and not q: return True if not p or not q: return False if p.val ! q.val: return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)「相同的树」判定的时间复杂度为 $O(\min(m, n))$它正是「另一棵树的子树」这道题最核心的构件外层枚举root的每一个节点内层用「相同的树」逻辑做逐树比对。三、解法一递归匹配双重 DFS这是关联文档给出的标准解法也是所有后续优化方案的基础。3.1 思路拆解题目要求检查root中是否存在一棵与subRoot完全相同的子树。自然想到的策略是遍历root中的每一个节点这一步是外层 DFS对每个节点判断「以该节点为根的整棵子树」是否与subRoot完全相同这一步是内层 DFS即isSameTree。为此定义两个递归函数isSameTree(p, q)判断两棵树p和q是否完全相同结构与节点值均一致isSubtree(root, subRoot)判断subRoot是否是root的子树。对于isSubtree的递归逻辑递归终止条件如果当前root为空返回False空树不可能包含非空的subRoot本层判断检查以当前root为根的树是否与subRoot相同递归向下继续在root.left和root.right中寻找只要任意一侧包含subRoot整体结果即为True。3.2 完整代码# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) - bool: # 判断两棵树是否完全相同 def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) - bool: if not p and not q: return True if not p or not q: return False return p.val q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right) # 如果 root 为空返回 False if not root: return False # 检查当前节点为根的树是否与 subRoot 相同 # 或者递归检查左右子树 return isSameTree(root, subRoot) or \ self.isSubtree(root.left, subRoot) or \ self.isSubtree(root.right, subRoot)3.3 递归执行过程以示例 1root [3,4,5,1,2]subRoot [4,1,2]为例递归过程如下isSubtree(root3, subRoot)isSameTree(3, 4)失败3 ! 4转向isSubtree(root.left4, subRoot)isSubtree(root4, subRoot)isSameTree(4, 4)两棵树的根节点值相等递归比较左子树isSameTree(1, 1)为True、右子树isSameTree(2, 2)为True因此整体返回True最终结果True。可以看出isSubtree是前序遍历式的外层 DFS先比较当前节点再递归左、右子树与 docs/05_tree/05_02_binary_tree_traverse.md 中二叉树前序遍历的递归模式完全一致。3.4 复杂度分析时间复杂度$O(m \times n)$其中 $m$ 是root的节点数$n$ 是subRoot的节点数。最坏情况下如root退化为一条链且每个节点都要完整比对一次subRoot外层需要检查root中的每个节点每次isSameTree比较需要 $O(n)$ 时间空间复杂度$O(m)$最坏情况下递归调用栈的深度为 $m$对应root退化为链的形态。需要说明的是这里的 $O(m \times n)$ 是最坏情况上界。当两棵树形态差异明显时例如根节点值不同isSameTree会在常数时间内提前返回实际运行远快于该上界。关于大 O 记号与最坏/平均复杂度分析的约定可参考 docs/00_preface/00_03_algorithm_complexity.md。四、解法二序列化 字符串匹配KMP 优化题目标签中包含「字符串匹配、哈希函数」暗示了更高级的思路把树结构问题转化为字符串匹配问题。4.1 思路拆解如果能把一棵二叉树「序列化」成一个唯一的字符串那么判断subRoot是否为root的子树就等价于判断subRoot的序列化串是否为root的序列化串的子串。具体步骤序列化分别对root和subRoot做前序遍历根 → 左 → 右同时用特殊标记如#表示空节点、用分隔符如,隔开节点值生成唯一的字符串字符串匹配在root的序列化串中查找subRoot的序列化串找到则返回true。注意两个细节必须标记空节点。如果不标记空节点root [2,3]与root [2,null,3]会得到相同的序列化结果无法区分结构差异必须使用分隔符。若不加分隔符root节点值为[12, 3]与[1, 23]可能产生歧义串。例如示例 1 中root [3,4,5,1,2]序列化为3,4,1,#,#,2,#,#,5,#,#subRoot [4,1,2]序列化为4,1,#,#,2,#,#后者显然是前者的子串。4.2 朴素匹配与 KMP 加速序列化后最简单的做法是使用朴素字符串匹配从root序列化串的每个位置开始尝试匹配subRoot串最坏时间复杂度为 $O((m n) \times n)$。而KMP 算法Knuth-Morris-Pratt可以在失配时利用已匹配前缀信息、让主串指针不回退将匹配时间复杂度降到 $O(m n)$。仓库中给出了完整的 KMP 实现见 codes/python/04_string/string_kmp.py其核心结构如下def kmp(T: str, p: str) - int: n, m len(T), len(p) next generateNext(p) # 生成 next 数组 j 0 # j 为模式串中当前匹配的位置 for i in range(n): # i 为文本串中当前匹配的位置 while j 0 and T[i] ! p[j]: # 匹配失败时模式串回退j 0 时停止回退 j next[j - 1] if T[i] p[j]: # 前缀匹配成功j 1 j 1 if j m: # 完全匹配成功返回匹配开始位置 return i - j 1 return -1 # 匹配失败返回 -1next数组的含义是next[j]记录模式串p[0: j1]中最长相等前后缀的长度。关于next数组的构建原理与 KMP 匹配过程的详细讲解见 docs/04_string/04_04_string_kmp.md。将 KMP 应用到本题整体复杂度为序列化$O(m n)$KMP 匹配$O(m n)$总时间复杂度$O(m n)$空间复杂度 $O(m n)$。相比递归匹配的 $O(m \times n)$当root节点数$m$与subRoot节点数$n$都较大时序列化 KMP 具有明显的渐进优势。不过需要注意序列化方案需要先完整遍历两棵树并构造字符串常数开销较大若root较小时递归匹配的实现在工程上往往更直接简单。五、解法三子树哈希Merkle 式自底向上标记题目标签中的「哈希函数」提示了另一种进阶思路为树中的每一棵子树计算一个哈希值然后比对哈希值。5.1 思路拆解自底向上为root中的每个节点计算「以其为根的子树」的哈希值例如def hash_subtree(node): if not node: return null return hash((hash_subtree(node.left), node.val, hash_subtree(node.right)))其中子树的哈希由「左子树哈希 当前节点值 右子树哈希」组合而成这与后序遍历左 → 右 → 根的递归顺序一致遍历细节见 docs/05_tree/05_02_binary_tree_traverse.md 2. 对subRoot计算同样的哈希值 3. 在遍历root的过程中一旦发现某棵子树的哈希值与subRoot的哈希值相等再调用isSameTree做最终确认防止哈希碰撞返回true。5.2 复杂度分析时间复杂度哈希的递归组合使得每个节点只被访问常数次整体为 $O(m n)$仅在哈希值相等时才会触发一次 $O(n)$ 的逐节点确认因此平均与最坏情况都在 $O(m n)$ 量级空间复杂度$O(m n)$用于存储各子树哈希值或递归栈。子树哈希思路本质上是一种「自底向上聚合信息」的模式与并查集、线段树等树形结构中「合并子问题信息」的思想一脉相承仓库中相关实现可参考 codes/python/05_tree/tree_unionFind.py。不过在实际面试中哈希方案需要对碰撞问题有所说明因此通常作为加分项思路呈现主流答案仍是递归匹配。六、三种解法对比与选型建议解法核心思想时间复杂度空间复杂度适用场景递归匹配双重 DFS外层枚举节点 内层isSameTree$O(m \times n)$$O(m)$通用、代码最简洁面试首选序列化 KMP树转字符串 KMP 子串匹配$O(m n)$$O(m n)$两棵树规模大、追求渐进最优子树哈希自底向上哈希 碰撞确认$O(m n)$$O(m n)$需要额外讲解哈希碰撞处理的进阶场景选型建议面试时优先给出递归匹配思路直观、实现短、无碰撞风险在回答时间复杂度的追问时可自然过渡到序列化 KMP 或子树哈希展示对 $O(m \times n)$ 上界的优化理解。七、相关题目与知识延伸本题在仓库中有完整的知识链路可以串联复习前置基础树的定义、二叉树性质与链式存储见 docs/05_tree/05_01_tree_basic.md遍历基础前序/中序/后序/层序遍历的递归与非递归实现见 docs/05_tree/05_02_binary_tree_traverse.md同源子问题LeetCode 0100「相同的树」是本题isSameTree辅助函数的独立版本见 docs/solutions/0100-0199/same-tree.md字符串匹配KMP 算法原理与next数组构建见 docs/04_string/04_04_string_kmp.md配套可运行的示例代码在 codes/python/04_string/string_kmp.py复杂度分析大 O 记号、最坏/平均复杂度约定见 docs/00_preface/00_03_algorithm_complexity.md同类题目索引本题在 0500-0599 分段的完整题解索引见 docs/solutions/0500-0599/index.md更多分类刷题清单见 docs/00_preface/00_06_categories_list.md。掌握「递归匹配」这道题的分解思路后遇到任何「判断树 A 是否包含树 B」「两棵树是否同构」「找出所有相同子树」类问题都可以复用「外层遍历 内层相等性判定」或「序列化/哈希归约到字符串/哈希问题」这两类范式。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐30分钟上手SQL注入测试CyberStrikeAI完整实战指南30分钟上手SQL注入测试CyberStrikeAI完整实战指南 手工构造注入 payload、逐条比对 HTTP 响应、再对着 WAF 拦截日志想办法绕过—网络安全渗透测试人工智能大模型AI AgentRAG后端前端MCP 服务漏洞扫描AlgoNote 题解精讲从前序与中序遍历序列构造二叉树LeetCode 0105 · 递归分治 哈希表优化AlgoNote 题解精讲从前序与中序遍历序列构造二叉树LeetCode 0105 · 递归分治 哈希表优化 本篇为「算法通关手册」AlgoNote教程文档知识库AlgoNote 算法题解LeetCode 0106 从中序与后序遍历序列构造二叉树递归分治全解析AlgoNote 算法题解LeetCode 0106 从中序与后序遍历序列构造二叉树递归分治全解析 本文是 AlgoNote「算法通关手册」二叉树还原专题教程文档知识库上一篇Serverless-Devs项目维护与升级版本管理、依赖更新与兼容性处理下一篇S4项目深度解析从HiPPO理论到实际应用的完整路线图创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考