示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕《程序员面试金典第 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] 输出truet1 以层序遍历表示为1 → 左孩子 2、右孩子 3其中以节点2为根的子树恰好只有它自己与 t2 完全一致因此返回true。示例 2输入t1 [1, null, 2, 4], t2 [3, 2] 输出falset1 的形态为1只有右子树1 → 右孩子 2 → 2 的左孩子 4。t2 为3带左孩子2。遍历 t1 的所有节点没有任何一棵子树能在结构与数值上同时等于 t22的左孩子是4而非空、3又不存在于 t1因此返回false。数据范围提示题目给出的节点数目范围为[0, 20000]。这意味着两棵树都可能为空树也意味着最坏情况下需要处理数万个节点的比较时间复杂度与空间复杂度的分析在实战中不可忽略。核心解法双层递归外层遍历 t1内层同步比对仓库在 README.md 中给出的标准解法是方法一递归。其整体策略可以概括为对 t1 的每个节点尝试把它当作与 t2 “对齐”的根节点对齐后要求结构与数值同时相等才算匹配成功。若当前节点对齐失败则转向 t1 的左、右孩子继续尝试。这一策略由两个层次组成内层dfs(t1, t2)同步地、一步步地比较两棵树的对应节点判断“以 t1 当前节点为根的子树”与“t2”是否完全相等外层checkSubTree(t1, t2)负责在 t1 中“搜索起点”——先尝试当前根节点失败后递归地尝试左子树与右子树。边界条件的判定逻辑解法中三个关键的空指针判定各语言实现完全一致条件返回值原因t2 为空true空树是任何树的子树约定t1 为空且 t2 非空false大树的该分支已耗尽仍找不到匹配当前节点值不相等false值不匹配直接剪枝无需继续深入其中内层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 的节点数为 nt2 的节点数为 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 3Solution.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 版对“结构完全一致”最直白的表达。JavaSolution.javaclass 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递归时使用||短路——只要左子树命中就不再搜索右子树这是典型的剪枝优化。CSolution.cppclass 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/!t2dfs中以!t1作为“t2 为空时 t1 也应为空”的等价写法与 Java 的t1 null语义一致。GoSolution.gofunc 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 标准且推荐的递归闭包写法。TypeScriptSolution.tsfunction 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兼容。RustSolution.rsuse std::cell::RefCell; use std::rc::Rc; impl Solution { fn dfs(t1: OptionRcRefCellTreeNode, t2: OptionRcRefCellTreeNode) - 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: OptionRcRefCellTreeNode, t2: OptionRcRefCellTreeNode, ) - 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 版本最能体现所有权与借用约束。树的节点类型为OptionRcRefCellTreeNodedfs通过Option...借用而非转移所有权进入Some分支后必须调用borrow()获得可变引用再访问val/left/right。外层搜索起点时使用Rc::clone增加引用计数以构造新的Some包装避免移动原始节点。SwiftSolution.swiftclass 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 可选链场景下的惯用写法。各语言实现对照小结语言内层函数命名空指针判定写法文件路径Python 3dfsis NoneSolution.pyJavadfs nullSolution.javaCdfs!ptrSolution.cppGodfs闭包 nilSolution.goTypeScriptdfs箭头函数!nodeSolution.tsRustdfs关联函数match模式Solution.rsSwiftisSameTree nil/!Solution.swift备选思路序列化 子串匹配以及为何容易出错README 的“思考”部分提到了一条值得讨论的备选路线判断 t2 是否与 t1 某棵子树完全相同序列化后做子串匹配可行但要处理分隔与空节点编码。其思想是将两棵树序列化为字符串如先序遍历然后判断 t2 的序列化结果是否是 t1 序列化结果的子串。这条路线可行但陷阱重重必须编码空节点若只序列化非空节点的值[1, 2]与[1, null, 2]会得到相同的前缀串导致错误匹配。因此空指针必须用占位符如#或null显式编码。必须使用分隔符不加分隔符时节点值12与1, 2无法区分例如12会被误认为1后接2。建议在节点值之间插入分隔符如,。复杂度并不更优序列化本身需要 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 仓库的通用约定。实战指引如何在本仓库中查看与验证阅读题解打开 README.md中文或 README_EN.md英文即可查看题目描述、示例与七语言解法。查看独立提交文件进入lcci/04.10.Check SubTree/目录按需选择Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.swift中的任意一个复制到 LeetCode 面试题 04.10 的代码区直接提交。本地运行以 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) 空间覆盖了全部边界情况并提供了七种主流语言的等价实现。相比序列化 子串匹配直接递归更简单、更不易出错。掌握本题后你可以将其思路迁移到“两棵树是否相同”“树的子结构”“子树中出现次数统计”等一揽子二叉树递归比对问题中。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐面试题 04.10 检查子树Check SubTree递归解法详解doocs/leetcode 多语言实现与边界辨析面试题 04.10 检查子树Check SubTree递归解法详解doocs/leetcode 多语言实现与边界辨析 本指南以 doocs/leetcod示例工程教程30分钟上手SQL注入测试CyberStrikeAI完整实战指南30分钟上手SQL注入测试CyberStrikeAI完整实战指南 手工构造注入 payload、逐条比对 HTTP 响应、再对着 WAF 拦截日志想办法绕过—网络安全渗透测试人工智能大模型AI AgentRAG后端前端MCP 服务漏洞扫描doocs/leetcode 题解精讲面试题 04.09 二叉搜索树序列BST Sequences——递归交织子序列算法详解doocs/leetcode 题解精讲面试题 04.09 二叉搜索树序列BST Sequences——递归交织子序列算法详解 本篇技术指南围绕 doocs示例工程教程上一篇5个简单步骤掌握Illustrator批量处理技巧下一篇HedgeDoc 2.0 FAQ 深度解析从 KaTeX 公式、Mermaid 图表到渲染器域名隔离的技术迁移指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考