LeetCode 572 子树判定（Subtree of Another Tree）：DFS 双递归与序列化 Z 函数两种解法全解析

LeetCode 572 子树判定（Subtree of Another Tree）：DFS 双递归与序列化 Z 函数两种解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

Subtree of Another Tree（子树判定）是二叉树上兼具递归思想与字符串技巧的经典问题：给定两棵二叉树root与subRoot，判断subRoot是否为root的子树。本文以本仓库的解题文档 articles/subtree-of-a-binary-tree.md 为骨架，完整讲解「DFS 双递归比较」与「序列化 + Z 函数模式匹配」两种解法，并结合仓库中 Python、C、Go、TypeScript、Rust、Ruby 等 12 种语言的真实实现进行交叉印证。读完本文，你将掌握子树判定的递归建模、sameTree辅助函数的正确写法，以及用线性时间字符串匹配把树比较问题降为 $O(m+n)$ 的高级技巧。

前置知识

在动手编码之前，先确认自己已经掌握以下三个基础模块，它们正是本问题两种解法的共同地基：

• 二叉树结构：理解节点由val、left、right组成，以及前序 / 中序 / 后序等遍历方式。
• 深度优先搜索（DFS）：本问题需要遍历主树的每一个节点，并在每个节点上递归比较子树。
• 树的相等性比较：两棵树相等，要求结构完全相同，且对应位置的节点值逐一相等。

文档 articles/subtree-of-a-binary-tree.md 开头明确列出了这三项前置要求，它们直接对应解法一的递归骨架与解法二的序列化编码。

一、解法一：DFS 双递归（暴力比较）

1.1 直觉：把大问题拆成「找位置」与「比相等」

子树判定的核心矛盾在于：subRoot可能出现在root的任意一个节点之下。于是我们把它拆成两个递归子问题：

1. 在主树中定位：用 DFS 遍历root的每一个节点，逐个尝试把该节点当作候选子树的根；
2. 在候选位置验证：对每个候选节点，调用辅助函数sameTree判断「以该节点为根的子树」与subRoot是否完全相同。

具体来说，对root中的每个节点：

• 若其值与subRoot根节点值相同，则完整比较两棵子树；
• 若完全相同，直接返回true；
• 否则继续向left和right两个孩子递归搜索。

sameTree辅助函数则负责逐节点精确比对：值相同且左子树相同且右子树相同，二者才相等。

1.2 算法步骤

isSubtree(root, subRoot)：

1. 若subRoot为空 → 返回true（空树是任何树的子树）；
2. 若root为空但subRoot非空 → 返回false；
3. 在当前root节点：若sameTree(root, subRoot)为真 → 返回true；
4. 递归检查isSubtree(root.left, subRoot)与isSubtree(root.right, subRoot)；
5. 任一侧返回true则整体返回true。

sameTree(root1, root2)：

1. 两个节点都为null→ 返回true；
2. 仅其中一个为null→ 返回false；
3. 节点值不同 → 返回false；
4. 递归检查左孩子与右孩子。

1.3 仓库源码印证：同一思路的多种语言表达

仓库 python/0572-subtree-of-another-tree.py 的实现与文档算法完全一致，且把辅助函数命名为isSameTree：

class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not subRoot: return True if not root: return False if self.isSameTree(root, subRoot): return True return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: if not p and not q: return True if p and q and p.val == q.val: return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right) else: return False

C 语言实现 展示了另一种组织方式：先比较值，只有值相等时才调用isSame做全量比对，然后用||串联左右子树的递归结果，并以compareTree兜底：

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if (root == NULL) { return false; } bool compareTree = false; if (root -> val == subRoot -> val) { compareTree = isSame(root, subRoot); } return (isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot) || compareTree); }

Go 实现 则用单行返回把「定位」与「验证」的递归关系表达得最紧凑：

func isSubtree(root *TreeNode, subRoot *TreeNode) bool { if root == nil { return false } return equals(root, subRoot) || isSubtree(root.Left, subRoot) || isSubtree(root.Right, subRoot) }

Rust 实现 额外展示了指针所有权语言下的写法：由于TreeNode被Rc<RefCell<>>包裹，比较时需要先borrow()再取val，递归时用clone()共享所有权，体现了同一算法在不同内存模型下的落地差异：

match (root, sub_root) { (_, None) => true, (None, _) => false, (Some(root), Some(sub_root)) => { if is_sametree(Some(root.clone()), Some(sub_root.clone())) { return true; } Solution::is_subtree(root.borrow().left.clone(), Some(sub_root.clone())) || Solution::is_subtree(root.borrow().right.clone(), Some(sub_root)) } }

1.4 复杂度分析

• 时间复杂度：$O(m \times n)$ —— 最坏情况下（例如subRoot反复与root中大量子树的前缀匹配失败），每个root节点都可能触发一次完整的sameTree扫描，其中 $n$ 是root的节点数，$m$ 是subRoot的节点数。
• 空间复杂度：$O(m + n)$ —— 两条递归链的调用栈深度之和（isSubtree链深度受root高度约束，sameTree链深度受subRoot高度约束），即文档给出的 $O(m + n)$。

二、解法二：序列化 + Z 函数模式匹配

2.1 直觉：把树比较降维成字符串匹配

解法一在「值匹配但结构不匹配」的场景下会重复浪费大量比较。解法二换了一个视角：先给两棵树各拍一张「字符串快照」，然后只需回答一个问题——S_sub是不是S_root的子串？

关键细节有两个，缺一不可：

1. 序列化必须保留null孩子：前序遍历中若不给空孩子打标记（如#），不同的树形会序列化成相同字符串，导致误判；
2. 必须使用分隔符（如$）：把「节点值」与「空标记」隔开，防止12与1、2这类相邻值粘连歧义。

序列化完成后，问题转化为标准的模式匹配问题，可用Z 函数（Z-function）或KMP在线性时间内求解，从而把整体复杂度从 $O(m \times n)$ 降到 $O(m + n)$。

2.2 算法步骤

1. 序列化一棵树：采用前序遍历；

   • 对每个非空节点：追加$+ 节点值；
   • 对每个null孩子：追加#$（或#）；
   • 这样结构和值都被唯一编码。

2. 构造字符串：

   • S_sub=subRoot的序列化结果；
   • S_root=root的序列化结果。

3. 拼接：combined = S_sub + "|" + S_root，其中|是序列化中不会出现的分隔符（防止模式串跨边界误匹配）。

4. 运行 Z 函数：对combined计算 Z 数组；设m = len(S_sub)，扫描S_root对应的区间：若存在某个位置i满足Z[i] == m，说明S_sub完整出现在该位置 → 返回true。

5. 扫描结束未命中 → 返回false。

扫描起点为什么是sub_len + 1？因为|占了一位，从S_sub的结尾之后才是S_root的起始位置，只有落在S_root内部的匹配才有效。

2.3 Python 参考实现（含 Z 函数）

文档给出的 Python 实现把序列化、Z 函数与主逻辑三个部分拆得清清楚楚，可直接复制运行：

class Solution: def serialize(self, root: Optional[TreeNode]) -> str: if root == None: return "$#" return ("$" + str(root.val) + self.serialize(root.left) + self.serialize(root.right)) def z_function(self, s: str) -> list: z = [0] * len(s) l, r, n = 0, 0, len(s) for i in range(1, n): if i <= r: z[i] = min(r - i + 1, z[i - l]) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] - 1 > r: l, r = i, i + z[i] - 1 return z def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: serialized_root = self.serialize(root) serialized_subRoot = self.serialize(subRoot) combined = serialized_subRoot + "|" + serialized_root z_values = self.z_function(combined) sub_len = len(serialized_subRoot) for i in range(sub_len + 1, len(combined)): if z_values[i] == sub_len: return True return False

Z 函数快速理解：Z[i]表示从位置i开始、与字符串前缀相同的最大长度。Z 算法的精妙之处在于维护区间[l, r]——当前已知的、与前缀匹配的最右区间。当i <= r时，可以复用区间内对称位置的Z[i - l]作为初始值（取min(r - i + 1, z[i - l])），再暴力扩展，从而把整体均摊复杂度降到线性。

2.4 仓库源码印证

解法二同样在仓库中能找到多语言落地方案。以 Go 实现 的姊妹版本（文档中的 Go 代码）为例，其serialize与 Z 函数结构与上文的 Python 版本一一对应：

func serialize(root *TreeNode) string { if root == nil { return "$#" } return "$" + strconv.Itoa(root.Val) + serialize(root.Left) + serialize(root.Right) } func zFunction(s string) []int { n := len(s) z := make([]int, n) l, r := 0, 0 for i := 1; i < n; i++ { if i <= r { z[i] = min(r-i+1, z[i-l]) } for i+z[i] < n && s[z[i]] == s[i+z[i]] { z[i]++ } if i+z[i]-1 > r { l = i r = i + z[i] - 1 } } return z }

仓库根目录 go/0572-subtree-of-another-tree.go 提供的是 DFS 版本，而文档 articles/subtree-of-a-binary-tree.md 中的 Go 片段为 Z 函数版本，二者互为补充。类似地，Java、C++、JavaScript、C#、Kotlin、Swift、Rust、Scala、Ruby 的实现均可在对应语言的0572-subtree-of-another-tree.*文件中找到（如 ruby/0572-subtree-of-another-tree.rb、typescript/0572-subtree-of-another-tree.ts），适合作为多语言对照学习材料。

2.5 复杂度分析

• 时间复杂度：$O(m + n)$ —— 序列化各遍历一遍树，Z 函数对总长为 $m + 1 + n$ 的字符串做线性扫描。
• 空间复杂度：$O(m + n)$ —— 存储S_sub、S_root、combined与 Z 数组。

三、常见误区（Common Pitfalls）

3.1 混淆「子树」与「子结构」

子树要求从某个节点向下直到所有叶子都完全一致。常见错误是只比较节点值相同就返回true，却没有验证根节点之下的完整结构。只要subRoot有孩子，这些孩子在主树对应位置必须存在且值匹配。仅仅在主树中找到值相同的节点是不够的——例如root = [3,4,5,1,2]、subRoot = [4,1]是合法子树，但若subRoot = [4,2]而root中 4 的左孩子是 1、右孩子是 2，则[4,2]不是root的子树（因为 4 的左孩子必须是null才算结构一致）。

3.2 树比较时空值处理错误

比较两棵树相等时，两棵树在相同位置必须有相同的null孩子。高频错误包括：

• 一个节点为null、另一个非null时却返回true；
• 只检查了左子树或右子树其中之一；
• 基例（base case）没有保证「要么同为null（返回true），要么都非空且值相同才继续递归」。

以文档的sameTree基例写法为准：

if not root and not subRoot: return True if root and subRoot and root.val == subRoot.val: # 继续递归左右 return False

Rust 实现 用match (a, b)把三种情况（都空 / 都非空 / 一空一非空）显式列出，正是对这种基例约束的严谨表达：

match (root, sub_root) { (None, None) => true, (Some(a), Some(b)) => { a.borrow().val == b.borrow().val && is_sametree(a.borrow().left.clone(), b.borrow().left.clone()) && is_sametree(a.borrow().right.clone(), b.borrow().right.clone()) } _ => false, }

四、两种解法对比与选型建议

选型建议：面试或日常刷题时解法一足够，且与 articles/same-binary-tree.md（判断两棵树是否相同）高度呼应，可作递进练习；当root规模很大、匹配失败频繁导致 $O(m \times n)$ 退化明显时，解法二通过序列化 + 线性模式匹配获得最坏情况下的稳定性能。相关进阶题还包括 articles/find-duplicate-subtrees.md（找重复子树）与 articles/count-univalue-subtrees.md（统计单值子树），它们同样建立在「子树结构比较」这一核心能力之上。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode