最近回刷二叉树题目觉得“算法10另一棵树的子树”这道题很值得拿出来细说。题面很短给你两棵二叉树 root 和 subRoot判断 root 中是否存在一棵子树它的结构和 subRoot 完全一致。对应 LeetCode 是 572 题很多课程把它放在二叉树递归的中级位置。我第一次刷的时候觉得这题简单无非是遍历加比较真正动手才发现很多边界问题并不好处理比如“子树”和“子结构”的区别、序列化后的歧义、递归退化成 O(mn) 的风险。如果把这题吃透你顺带能把树的递归、字符串匹配、KMP、树哈希这些知识点全部串起来性价比非常高。适合刚学完二叉树遍历准备刷题、想系统理解递归设计或者想从一道题延伸出多种解的读者。1. 子树匹配到底在考什么1.1 题目里的“子树”是怎么定义的先看一个最直白的例子。假设 root 是[3,4,5,1,2]subRoot 是[4,1,2]那么 root 里以节点 4 为根的那棵子树正好就是[4,1,2]所以答案是 true。这里要注意“子树”并不是只看某个节点的值等于 subRoot 的根节点值就够了而是要求从 root 里的某个节点出发后面所有子孙节点、左右孩子关系都必须和 subRoot 一模一样连空节点都不能多出来。举个反例如果 root 的结构是节点 4 的左孩子 1 下面还挂着一个 0那么即使存在子路径4 - 1它的子树也不是[4,1,2]因为 subRoot 里的节点 1 没有左孩子而 root 里的节点 1 有左孩子。所以这道题的本质是把 root 当成一个“容器树”在里面寻找每一个可能的起点判断从这个起点开始往下的整棵子树是否和 subRoot 完全相同。1.2 最容易混淆的概念子树不等于子结构网上很多讨论会把 LeetCode 572 和剑指 Offer 26“树的子结构”放在一起因为两张图长得非常像。但它们有一个关键差异子树要求完全匹配到叶子节点而子结构允许匹配到某个位置就提前结束。我打个比方。子树匹配就像是拿一张印章盖在纸上要求印章覆盖到的每一个点都必须和纸上的图案完整重合不能多出一笔。子结构匹配则像是从一棵树上“剪下一段枝干”你只要这段枝干的形状能对应上目标树的一部分就行至于这段枝干原来的位置下面还有没有更细的枝条不影响判断。在递归代码里这个差异体现在终止条件上判断子树时双方同时为空才算匹配到叶子结束判断子结构时只要 subRoot 那边为空就可以返回 true即使当前 root 这边的节点下面还有子节点也没关系。很多初学者把剑指 Offer 那套 isMatch 代码原封不动搬到 LeetCode 572 上结果会出现“多出来的节点也被忽略”的错误本质上就是没分清这两个概念。2. 解法一双重递归暴力匹配2.1 递归函数的设计思路暴力匹配法非常直观核心由两个递归函数组成isSameTree(p, q)判断以 p 和 q 为根的两棵树是否完全一样isSubtree(root, subRoot)遍历 root 上每一个节点分别以这些节点作为起点调用isSameTree比较。先说isSameTree。两棵树相同必须同时满足三个条件根节点值相等、左子树相同、右子树相同。递归到双方都为空的时候说明一路比较下来没有发现不一致返回 true如果一边空一边不空说明结构不同立即返回 false。def is_same_tree(p, q): if p is None or q is None: return p is q return p.val q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)这里用p is q处理两个空节点的情况逻辑很紧凑如果 p 和 q 都是空返回 True如果只有一个为空返回 False。主函数isSubtree是在 root 上做遍历。对每个节点先看以它开头能否和 subRoot 完全匹配如果不行再往左右子树递归查找。def is_subtree(root, subRoot): if root is None: return False if is_same_tree(root, subRoot): return True return is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)两个函数嵌套起来逻辑并不复杂但剪枝要注意is_subtree(root.left, subRoot)和右子树的递归是或的关系只要左边找到就不用再找右边短路求值能省掉一部分无效递归。2.2 这段代码的复杂度到底是多少假设 root 有 m 个节点subRoot 有 n 个节点。isSameTree在最坏情况下会比较完一整棵小树也就是 O(n)。而在isSubtree里外层需要遍历 root 的全部 m 个节点并且在每个节点上都可能触发一次isSameTree。因此最坏时间复杂度是 O(m×n)。空间复杂度主要来自递归栈。两层递归都会占用调用栈最坏情况下树退化成链状递归深度接近节点数所以空间复杂度是 O(m)。很多人觉得这题用暴力法就能过实际上 LeetCode 的数据规模并不算大m 和 n 都在 10^4 量级时有些测试用例会让暴力法跑得很吃力甚至超时。特别是当树的结构高度相似时问题会更明显。2.3 什么情况下会退化到 O(mn)我构造过一组极端数据一棵 root 是一条左斜链每个节点值都和 subRoot 根节点值相同subRoot 也是一条长长的链。比如 root 是 100 个节点组成的单链表形状subRoot 是 50 个节点组成的单链表形状。这种情况下外层遍历 root 的每个节点时都会走进isSameTree做一次近乎完整的匹配。每次都在链的尾部才意识到不匹配于是整体复杂度就接近 100×50。虽然这个例子数据不大但放到上万节点时暴力法很容易成为性能瓶颈。这也是我推荐继续看后面两种解法的原因它们把 O(mn) 优化到了 O(mn)思路也更能体现算法设计的层次感。3. 解法二把树序列化成字符串再匹配3.1 为什么要把树转成字符串暴力法的问题在于每个节点都要重新和 subRoot 做一次结构比较成本很高。那么有没有更“整体”一点的办法一个自然的想法是既然要比较“子结构是否完全一样”能不能把 root 里的所有子树信息编码成一个长字符串把 subRoot 也编码成一个较短字符串然后直接判断第二个字符串是不是第一个字符串的子串举个例子subRoot 如果是4,1,#,#,2,#,#而 root 序列化后的字符串恰好包含这一段那说明 root 中出现了相同结构。这种思路能够成立的关键是序列化必须保证“树的结构”和“字符串”一一对应否则会出现两棵不同的树编码成相同字符串导致判断错误。3.2 序列化的三个关键细节我在写序列化代码时踩过几个坑这里逐个说明。第一必须标记空节点。如果不标记空节点树 A 是“根为 2、左孩子为 1”树 B 是“根为 2、右孩子为 1”普通前序遍历都会输出2,1根本无法区分。解决方法是遇到空节点时输出一个特殊占位符比如#。带占位符之后树 A 序列化为2,1,#,#,#树 B 序列化为2,#,1,#,#两者立刻就能区分开。第二节点值之间要加分隔符。比如一个节点值是整数 12另一个节点值是 1 和 2 两棵子树如果不加逗号12可能被错误切分为1和2。所以字符串拼接时节点值之间必须用逗号等符号隔开。第三建议使用前序遍历或后序遍历。前序遍历从根开始递归理解成本最低。后序遍历也可以。中序遍历配合空节点也能实现但由于中序遍历天然会把左子树放在前面部分场景下不如前序直观。我统一用前序递归。def serialize(node): if node is None: return # return str(node.val) , serialize(node.left) , serialize(node.right)输出格式类似3,4,1,#,#,2,#,#,5,#,#。3.3 匹配阶段KMP 换掉朴素查找字符串序列化完成之后问题就变成在一个长串 big 中查找是否存在另一个串 small。如果直接写两个 for 循环做朴素子串匹配算法复杂度是 O(len(big)×len(small))在树节点很多的情况下并不比暴力法好到哪去。Python 的in运算符底层虽然做过优化但面试官大概率希望你能讲出更明确的算法结构所以这里值得用 KMP。KMP 的核心思想是当匹配失败时不把 big 串的指针回退到开头而是根据已经匹配过的信息把 small 串的指针回退到一个合适的位置从而让 big 串只遍历一次。这需要预先计算 small 串的 next 数组。3.4 手写 KMP 的代码和 next 数组next 数组的含义是对于 small 串的每个位置 inext[i]表示 small[0..i] 这段前缀中最长的相等前后缀的长度。比如模式串是ababcnext[3]对应的子串是abab它的最长相等前后缀是ab所以next[3] 2。下面的代码是完整可跑的版本我把构建 next 和匹配过程分成了两个函数。def build_next(pattern): nxt [0] * len(pattern) j 0 for i in range(1, len(pattern)): while j 0 and pattern[i] ! pattern[j]: j nxt[j - 1] if pattern[i] pattern[j]: j 1 nxt[i] j return nxt def kmp_contains(text, pattern): if not pattern: return True nxt build_next(pattern) j 0 for ch in text: while j 0 and ch ! pattern[j]: j nxt[j - 1] if ch pattern[j]: j 1 if j len(pattern): return True return False使用时只需要把 root 序列化得到 big把 subRoot 序列化得到 small然后调用kmp_contains(big, small)即可。整个方案的时间复杂度是序列化 O(mn) 加 KMP O(mn)整体线性比暴力法稳定很多。空间复杂度是 O(mn)主要花在序列化字符串和 next 数组上。4. 解法三给子树编一个指纹4.1 序列化方案的隐藏开销序列化加 KMP 虽然把时间优化到了线性但它有一个额外开销为了构造 root 的长字符串每个节点的信息都会被展开一次。这本身没有问题但如果你还想进一步压缩空间或者希望在一次遍历中直接判断可以考虑给每一棵子树算一个独一无二的“指纹”编号。这个思路有点像现实中的档案管理。我不需要每次重新写一遍整个部门的人员名单来判断两个部门是否完全相同只需要给每个部门编一个唯一编号相同结构的人员树会得到相同编号不同结构得到不同编号。判断子树关系时直接比较编号就行。4.2 使用后序遍历给子树分配唯一 ID具体做法是选一棵子树用它的根节点值、左子树编号、右子树编号共同组成一个键不同键分配不同的编号。因为左子树编号和右子树编号已经递归包含了整棵子树的全部结构信息所以这个键足以代表当前子树的完整结构。我把空树编号固定为 0。对于每个非空节点先递归计算左子树编号再递归计算右子树编号用三元组(node.val, left_id, right_id)作为键如果键没有出现过就分配一个新的编号如果键出现过说明之前已经有相同结构的子树直接复用之前编号。def compute_ids(root, subRoot): mapper {} def get_id(node): if node is None: return 0 left_id get_id(node.left) right_id get_id(node.right) key (node.val, left_id, right_id) if key not in mapper: mapper[key] len(mapper) 1 return mapper[key] def is_same_tree(p, q): if p is None or q is None: return p is q return p.val q.val and is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right) target_id get_id(subRoot) def dfs(node): if node is None: return False if get_id(node) target_id and is_same_tree(node, subRoot): return True return dfs(node.left) or dfs(node.right) return dfs(root)这段代码把编号计算和遍历 tree 的过程合在了一起。由于get_id是后序的计算流程当它返回到某个节点时当前节点的左右子树编号都已经确定因此能够正确生成当前子树的编号。为什么最后还要再用is_same_tree二次确认一次因为虽然这里的 mapper 方案本身理论上没有碰撞但实际工程中如果改用更激进的哈希方式比如用hash((node.val, left_hash, right_hash))之类压缩固定位数的方案不同结构是可能碰撞的。把二次确认留在那里可以给方案上一层保险。即使编号完全一样我再逐节点核对一次既然哈希都相等真正去核对时大部分情况很快返回 true性能损失可以接受。4.3 数组结构与普通哈希方案的区别有人会问既然 mapper 里的 key 还是由三元组构成那和重新把树序列化一次有什么区别区别在于复用。序列化方案里每个子树如果都要存成完整字符串最坏情况下空间会累计成 O(m²)而编号方案里每个节点的三元组只出现一次左子树编号和右子树编号都是整数总空间只有 O(m)。如果你希望代码更贴近传统意义下的“哈希树”也可以这样写def tree_hash(node): if node is None: return 0 left_hash tree_hash(node.left) right_hash tree_hash(node.right) return (node.val * 1000003 left_hash * 131 right_hash * 97) % (10 ** 9 7)这种写法本质上把整棵子树的信息压缩成一个整数速度更快但因为取模和乘法的存在理论上存在碰撞风险。所以判断哈希相等之后务必再用isSameTree做一次完整校验。这也是我在工程代码里惯用的稳健写法。5. 从这道题延伸出去的变化题5.1 变体一判断子结构是否存在如果面试官把题目改一下说只需要判断 subRoot 是否能匹配 root 中某个“不一定要延伸到叶子”的结构那就是我在开头提到过的“子结构”问题。此时的递归终止条件需要修改def is_match(p, q): if q is None: return True if p is None: return False if p.val ! q.val: return False return is_match(p.left, q.left) and is_match(p.right, q.right) def has_substructure(root, sub): if root is None or sub is None: return False if is_match(root, sub): return True return has_substructure(root.left, sub) or has_substructure(root.right, sub)两个变体做题时的差异可以整理成表格比较项子树问题572子结构问题剑指 Offer 26q 为空时还需要看 p 是否为空直接返回 truep 为空但 q 不为空返回 false返回 false匹配终点双方都走到空允许 q 先结束典型用途判断完整子树存在判断局部结构匹配5.2 变体二统计子树出现次数如果题目不是问是否存在而是问 root 中有多少棵子树和 subRoot 完全一样那用树哈希方案会非常方便。你在遍历 root 计算每个节点子树编号的过程中维护一个计数器当前节点编号等于 target_id 时计数加一继续向左右子树递归最终返回计数。如果是序列化加 KMP也可以用 KMP 统计模式串在长串中出现了多少次只要在匹配成功时不提前 return而是记录位置并让 j 回退到next[j-1]继续匹配。5.3 这类“嵌套结构匹配”在真实开发里的位置我在日常开发中不太会遇到直接让你写“判断另一个树的子树”的业务但这类嵌套结构匹配的思想其实很常见。比如前端两个组件树做结构 diff需要判断某一段子组件树是否有变化或者代码静态分析中需要在一棵语法分析树 AST 里查找某个特定模式再比如配置文件是树形结构时想判断某一段配置是否完整出现在另一个大配置里。这些场景的共同点都是内容嵌套、节点有值和孩子、需要判断某个局部结构是否“等于”另一个结构。理解了这道题的三种解法你在面对类似问题时至少能说出两条路一条是序列化后做模式匹配一条是给子树算哈希值做节点级比较。6. 踩坑记录与调试建议6.1 高频错解速查表我把自己刷题时见过的问题整理成了下面这张表基本覆盖了这题 90% 的典型错误错误类型错误表现原因与解决混淆子树与子结构多出来的节点被忽略返回了错误的 true把 q 为空的终止条件改回双方必须同时为空不标记空节点左右孩子互换的结构无法区分序列化时遇到空节点输出#节点值忘记分隔符12 和 1,2 被看成一样每个节点值之间用逗号隔开只用值相等判断当前节点值等于 subRoot 根节点值就直接返回 true必须递归验证整棵子树结构root 为空直接访问属性空指针异常递归开头优先判断 root 是否为空暴力法在小规模通过大规模超时O(mn) 太慢改用 KMP 或树哈希方案KMP next 数组计算错误匹配结果不稳定用短字符串手动推一遍 next 再套代码这里尤其想强调空节点占位符的问题。实际工作中很多序列化工具为了省空间会省略空节点但在“用来判断结构是否一致”的场景下省略空节点会让左右子树信息丢失。这个问题我一开始也忽略过后来构造了一个反例才发现。6.2 调试树结构题目的三个顺手方法树形结构的 bug 不如普通数组那么好定位我平时调试主要用三个方法。第一个方法是在纸上画出小规模树。尽量把测试用例控制在三到五个节点例如测试 root 为[2,null,1]、subRoot 为[2,1]这种反例能快速暴露“空节点没有被正确比较”的问题。第二个方法是打印递归栈。如果怀疑递归进入顺序有误可以在函数入口打印带缩进的信息def is_subtree(root, subRoot, depth0): prefix * depth print(f{prefix}visit node: {root.val if root else None}) ...观察输出时重点看递归是否重复访问了已经比较过的节点或者某个子树是否因为短路逻辑没被访问。第三个方法是打印序列化字符串。字符串正确的情况下判断子树的问题就转换成了肉眼可直接检查的子串问题。如果序列化输出和预期不一致通常能很快定位是递归顺序写错还是分隔符处理有问题。6.3 这道题建议按什么顺序学我个人非常推荐按“暴力递归 - 序列化 KMP - 树哈希”的顺序练这道题不要一步到位直接背最优解。先写暴力递归能帮你巩固递归拆解能力明白isSameTree和isSubtree各自承担什么职责。接着做序列化你会被迫思考“什么信息能唯一决定一棵树”空节点占位符和分隔符的重要性只有自己踩一脚才记得住。最后再上 KMP 或树哈希你会自然理解为什么需要 next 数组、为什么哈希比较之后还要二次确认。面试如果问这道题我的建议也是从暴力法开始回答再逐步提出“可以优化到 O(mn)”。这样既能让面试官看到你的思考路径也避免一上来就给出复杂解法却讲不清动机的尴尬。算法题真正值钱的从来不是背代码而是从暴力解走向优化解时那几个“为什么”。