企业官网建设流程全解析

• 示例工程
• 教程

本文围绕《程序员面试金典（第 6 版）》中的面试题 04.10「检查子树」展开，深入讲解“判断一棵二叉树是否为另一棵二叉树的子树”这一经典算法问题，并结合 doocs/leetcode 仓库中 Python、Java、C++、Go、TypeScript、Rust、Swift 七种语言的官方实现，逐层剖析递归解法的思路、边界条件、复杂度，以及序列化 + 子串匹配等备选方案。读完本文，你将掌握子树判定问题的完整分析框架，并能直接套用仓库内任一语言的 Solution 代码完成 LeetCode LCCI 04.10 的实战作答。

题目概述：什么是“检查子树”

题目原文（见 README_EN.md）描述如下：

T1 和 T2 是两棵非常大的二叉树，T1 远大于 T2。设计一个算法，判断 T2 是否为 T1 的子树。

所谓“T2 是 T1 的子树”，指的是：存在 T1 中的某个节点 n，使得以 n 为根的子树与 T2 完全一致。换句话说，如果从节点 n 处把 T1 “砍断”，得到的这棵树与 T2 一模一样。

这里有一个容易混淆的关键点需要先厘清：题目要求的是子树（subtree），即结构完全一致、且从某个节点开始完整地包含其全部后代；这与《程序员面试金典》中常见的另一类问题——判断“一棵树是否是另一棵树的一个子结构/子串形态”（只需部分结构匹配）——并不相同。子树判定要求 t2 的每个节点（包括空指针位置）都与 t1 中以 n 为根的那棵子树逐一对齐。

输入输出示例

示例 1

输入：t1 = [1, 2, 3], t2 = [2] 输出：true

t1 以层序遍历表示为1 → 左孩子 2、右孩子 3，其中以节点2为根的子树恰好只有它自己，与 t2 完全一致，因此返回true。

示例 2

输入：t1 = [1, null, 2, 4], t2 = [3, 2] 输出：false

t1 的形态为1只有右子树：1 → 右孩子 2 → 2 的左孩子 4。t2 为3带左孩子2。遍历 t1 的所有节点，没有任何一棵子树能在结构与数值上同时等于 t2（2的左孩子是4而非空、3又不存在于 t1），因此返回false。

数据范围提示

题目给出的节点数目范围为[0, 20000]。这意味着两棵树都可能为空树，也意味着最坏情况下需要处理数万个节点的比较，时间复杂度与空间复杂度的分析在实战中不可忽略。

核心解法：双层递归（外层遍历 t1，内层同步比对）

仓库在 README.md 中给出的标准解法是方法一：递归。其整体策略可以概括为：

对 t1 的每个节点，尝试把它当作与 t2 “对齐”的根节点；对齐后要求结构与数值同时相等才算匹配成功。若当前节点对齐失败，则转向 t1 的左、右孩子继续尝试。

这一策略由两个层次组成：

1. 内层dfs(t1, t2)：同步地、一步步地比较两棵树的对应节点，判断“以 t1 当前节点为根的子树”与“t2”是否完全相等；
2. 外层checkSubTree(t1, t2)：负责在 t1 中“搜索起点”——先尝试当前根节点，失败后递归地尝试左子树与右子树。

边界条件的判定逻辑

解法中三个关键的空指针判定（各语言实现完全一致）：

其中内层dfs的退出条件更为严格：只有当 t2 为空时 t1 也必须为空，才返回true——这正是“子树要求结构完全一致”的体现：如果 t2 已经走完而 t1 这边还有多余的节点，说明多出来的部分不属于匹配范围，结构不相等。

正确性推演

• 若 t1 与 t2 在根节点即相等（dfs全绿），直接返回true；
• 否则问题缩小为：checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2)，即“t2 是否是 t1 左子树的子树”或“t2 是否是 t1 右子树的子树”；
• 递归继续下沉，直到某个节点对齐成功，或 t1 被遍历完毕（返回false）。

复杂度分析

设 t1 的节点数为 n，t2 的节点数为 m：

• 时间复杂度：最坏情况 O(n × m)。在 t1 接近退化为链表、且每个节点都要与 t2 完整比对时，退化为文档给出的 O(n²)（n 为 t1 节点数）。平均情况下匹配起点通常较早命中，实际运行会明显优于最坏界。
• 空间复杂度：O(n)。递归调用栈的最大深度由树高决定，最坏情况下（链状树）为 O(n)。

七语言源码级实现详解

仓库为本题提供了 7 种语言的独立实现文件，分别位于lcci/04.10.Check SubTree/目录下的Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.swift。它们与 README 中的代码一一对应，算法骨架完全相同，差异仅在语言特性上。以下逐语言拆解。

Python 3（Solution.py）

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def checkSubTree(self, t1: TreeNode, t2: TreeNode) -> bool: def dfs(t1, t2): if t2 is None: return t1 is None if t1 is None or t1.val != t2.val: return False return dfs(t1.left, t2.left) and dfs(t1.right, t2.right) if t2 is None: return True if t1 is None: return False if dfs(t1, t2): return True return self.checkSubTree(t1.left, t2) or self.checkSubTree(t1.right, t2)

要点：Python 版本利用is None做身份判断；外层递归通过self.checkSubTree显式调用来实现“换起点”的搜索。注意dfs内部判断t2 is None时返回t1 is None，这是 Python 版对“结构完全一致”最直白的表达。

Java（Solution.java）

class Solution { public boolean checkSubTree(TreeNode t1, TreeNode t2) { if (t2 == null) { return true; } if (t1 == null) { return false; } if (dfs(t1, t2)) { return true; } return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2); } private boolean dfs(TreeNode t1, TreeNode t2) { if (t2 == null) { return t1 == null; } if (t1 == null || t1.val != t2.val) { return false; } return dfs(t1.left, t2.left) && dfs(t1.right, t2.right); } }

要点：Java 版本将内层比对提取为私有方法dfs，外层checkSubTree递归时使用||短路——只要左子树命中就不再搜索右子树，这是典型的剪枝优化。

C++（Solution.cpp）

class Solution { public: bool checkSubTree(TreeNode* t1, TreeNode* t2) { if (!t2) { return true; } if (!t1) { return false; } if (dfs(t1, t2)) { return true; } return checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2); } bool dfs(TreeNode* t1, TreeNode* t2) { if (!t2) { return !t1; } if (!t1 || t1->val != t2->val) { return false; } return dfs(t1->left, t2->left) && dfs(t1->right, t2->right); } };

要点：C++ 使用指针判空!t1/!t2；dfs中以!t1作为“t2 为空时 t1 也应为空”的等价写法，与 Java 的t1 == null语义一致。

Go（Solution.go）

func checkSubTree(t1 *TreeNode, t2 *TreeNode) bool { var dfs func(t1, t2 *TreeNode) bool dfs = func(t1, t2 *TreeNode) bool { if t2 == nil { return t1 == nil } if t1 == nil || t1.Val != t2.Val { return false } return dfs(t1.Left, t2.Left) && dfs(t1.Right, t2.Right) } if t2 == nil { return true } if t1 == nil { return false } if dfs(t1, t2) { return true } return checkSubTree(t1.Left, t2) || checkSubTree(t1.Right, t2) }

要点：Go 没有方法重载与内部函数提前声明的限制，这里用闭包var dfs func(...) bool实现递归自引用，是 Go 标准且推荐的递归闭包写法。

TypeScript（Solution.ts）

function checkSubTree(t1: TreeNode | null, t2: TreeNode | null): boolean { const dfs = (t1: TreeNode | null, t2: TreeNode | null): boolean => { if (!t2) { return !t1; } if (!t1 || t1.val !== t2.val) { return false; } return dfs(t1.left, t2.left) && dfs(t1.right, t2.right); }; if (!t2) { return true; } if (!t1) { return false; } if (dfs(t1, t2)) { return true; } return checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2); }

要点：TS 借助TreeNode | null联合类型保证空指针安全；用!t1统一处理null与undefined，与题目给定的节点定义left?: TreeNode | null兼容。

Rust（Solution.rs）

use std::cell::RefCell; use std::rc::Rc; impl Solution { fn dfs(t1: &Option<Rc<RefCell<TreeNode>>>, t2: &Option<Rc<RefCell<TreeNode>>>) -> bool { match (t1, t2) { (Some(node1), Some(node2)) => { let n1 = node1.borrow(); let n2 = node2.borrow(); n1.val == n2.val && Solution::dfs(&n1.left, &n2.left) && Solution::dfs(&n1.right, &n2.right) } (None, Some(_)) => false, (Some(_), None) => false, _ => true, // Both are None } } pub fn check_sub_tree( t1: Option<Rc<RefCell<TreeNode>>>, t2: Option<Rc<RefCell<TreeNode>>>, ) -> bool { match (t1, t2) { (Some(node1), Some(node2)) => { let n1 = node1.borrow(); let n2 = node2.borrow(); Solution::dfs(&Some(Rc::clone(&node1)), &Some(Rc::clone(&node2))) || Solution::check_sub_tree(n1.left.clone(), Some(Rc::clone(&node2))) || Solution::check_sub_tree(n1.right.clone(), Some(Rc::clone(&node2))) } (Some(_), None) => true, (None, Some(_)) => false, _ => true, // Both are None or t1 is None } } }

要点：Rust 版本最能体现所有权与借用约束。树的节点类型为Option<Rc<RefCell<TreeNode>>>，dfs通过&Option<...>借用而非转移所有权；进入Some分支后必须调用borrow()获得可变引用再访问val/left/right。外层搜索起点时使用Rc::clone增加引用计数以构造新的Some包装，避免移动原始节点。

Swift（Solution.swift）

class Solution { func checkSubTree(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool { if t2 == nil { return true } if t1 == nil { return false } if isSameTree(t1, t2) { return true } return checkSubTree(t1!.left, t2) || checkSubTree(t1!.right, t2) } private func isSameTree(_ t1: TreeNode?, _ t2: TreeNode?) -> Bool { if t1 == nil && t2 == nil { return true } if t1 == nil || t2 == nil { return false } if t1!.val != t2!.val { return false } return isSameTree(t1!.left, t2!.left) && isSameTree(t1!.right, t2!.right) } }

要点：Swift 版本把内层比对命名为isSameTree，语义更贴近“两棵树是否相同”；在确认t1 != nil后使用强制解包t1!访问左右孩子，这是 Swift 可选链场景下的惯用写法。

各语言实现对照小结

备选思路：序列化 + 子串匹配（以及为何容易出错）

README 的“思考”部分提到了一条值得讨论的备选路线：

判断 t2 是否与 t1 某棵子树完全相同，序列化后做子串匹配可行，但要处理分隔与空节点编码。

其思想是：将两棵树序列化为字符串（如先序遍历），然后判断 t2 的序列化结果是否是 t1 序列化结果的子串。这条路线可行但陷阱重重：

1. 必须编码空节点：若只序列化非空节点的值，[1, 2]与[1, null, 2]会得到相同的前缀串，导致错误匹配。因此空指针必须用占位符（如#或null）显式编码。
2. 必须使用分隔符：不加分隔符时，节点值12与1, 2无法区分，例如12会被误认为1后接2。建议在节点值之间插入分隔符（如,）。
3. 复杂度并不更优：序列化本身需要 O(n) 时间，而朴素子串匹配最坏也是 O(n × m)；若改用 KMP 等线性子串算法虽可降至 O(n + m)，但工程实现复杂度显著高于双层递归。

因此，仓库的标准解法选择直接递归比对，语义清晰、实现简洁、对任何节点值分布都稳健。

从源码结构看本题在仓库中的组织方式

从仓库目录结构可以推断，本题属于lcci/（《程序员面试金典（第 6 版）》）系列题解，每个题目目录统一命名为“题号 + 题名”，内部固定包含：

• README.md/README_EN.md：中英文题解，包含题目描述、示例、数据范围、解法说明与多语言代码（tab 切换展示）；
• Solution.<ext>：对应语言的标准提交代码文件，与 README 中展示的代码保持一致。

lcci/目录下还有lcci.json与README.md等汇总文件，用于串联整套金典题解；lcci/README.md 可查看完整题单。这种“README 讲解 + 独立 Solution 文件”的组织方式，使得读者既可以阅读思路，也可以直接复制单文件代码到 LeetCode 提交，是 doocs/leetcode 仓库的通用约定。

实战指引：如何在本仓库中查看与验证

1. 阅读题解：打开 README.md（中文）或 README_EN.md（英文），即可查看题目描述、示例与七语言解法。
2. 查看独立提交文件：进入lcci/04.10.Check SubTree/目录，按需选择Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.swift中的任意一个，复制到 LeetCode 面试题 04.10 的代码区直接提交。
3. 本地运行（以 Python 为例）：在本地构造 TreeNode 并调用Solution().checkSubTree(t1, t2)，可自行验证示例：

# 构造 t1 = [1, 2, 3]（层序），t2 = [2] t1 = TreeNode(1) t1.left = TreeNode(2) t1.right = TreeNode(3) t2 = TreeNode(2) print(Solution().checkSubTree(t1, t2)) # True

其他语言同理，只需按对应文件的 TreeNode 定义构造树即可。注意：题目数据范围[0, 20000]意味着递归深度最坏可能达到 20000 层，Python / Java 等语言在极端链状输入下需留意递归栈限制；这也是 README 中复杂度分析强调空间复杂度 O(n) 的原因。

总结

面试题 04.10「检查子树」的核心可归纳为一句话：在 t1 中搜索能与 t2 完全对齐的根节点，并用同步递归校验结构与数值的逐节点一致。doocs/leetcode 仓库给出的双层递归解法（外层checkSubTree换起点、内层dfs/isSameTree做对齐比对）以 O(n²) 最坏时间、O(n) 空间覆盖了全部边界情况，并提供了七种主流语言的等价实现。相比序列化 + 子串匹配，直接递归更简单、更不易出错。掌握本题后，你可以将其思路迁移到“两棵树是否相同”“树的子结构”“子树中出现次数统计”等一揽子二叉树递归比对问题中。

• 示例工程
• 教程