LeetCode-Go 题解 0572Subtree of Another Tree另一棵树的子树递归解法剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 572 题“Subtree of Another Tree另一棵树的子树”展开讲解如何用 Go 语言判断一棵二叉树t是否是另一棵二叉树s的子树。文章以 leetcode/0572.Subtree-of-Another-Tree/README.md 为核心骨架结合仓库内 572. Subtree of Another Tree.go 的完整实现与 572. Subtree of Another Tree_test.go 的测试用例深入剖析“双重递归”解法、与第 100 题“Same Tree”的关系、复杂度边界以及在实际工程测试中的验证方式。读完本文你将掌握子树判定问题的标准递归套路并能直接用仓库中的代码在本地运行、验证与扩展。题目定义什么才算“另一棵树的子树”原文档给出的题目描述见 README.md给定两个非空二叉树 s 和 t检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看作它自身的一棵子树。翻译成算法语言需要同时满足两个条件结构相同子树必须从s的某个节点出发向下包含该节点的全部后代节点中间不能断开也不能只取某一部分后代节点值相同对应位置的节点值必须完全一致。“s 也可以看作它自身的一棵子树”这句话是一个容易被忽略但至关重要的判定当s与t完全相等时结果必须为true。仓库中的实现正是在递归入口最先检查“两棵树完全相同”正是对这一要求的落实。题目给出的两个示例示例 1 中树s为3 / \ 4 5 / \ 1 2树t为4 / \ 1 2t恰好是s中“以节点 4 为根”的那棵子树结构和节点值完全一致返回true。示例 2 中树s变为3 / \ 4 5 / \ 1 2 / 0树t仍为4 / \ 1 2此时以 4 为根的子树中还多出节点 0与t不再同构返回false。注意s的其他任意子树中也不存在与t完全相同的结构例如以 2 为根的子树只有单个节点因此整体结果是false。解题思路三分支递归框架原文档 README.md 明确指出这一题比较简单针对 3 种情况依次递归判断第一种情况s和t是完全一样的两棵树第二种情况t是s左子树中的子树第三种情况t是s右子树中的子树。第一种情况判断两棵树是否完全一致是第 100 题的原题。这套框架的精髓在于把“子树判定”拆解为两个层次的问题外层递归问题归约isSubtree(s, t)要么直接命中“两棵树完全相同”要么把问题缩小到s的左子树s.Left或右子树s.Right上继续递归内层递归同构判定“两棵树完全相同”本身又是一个递归问题需要同时比较节点值、左子树、右子树这正是第 100 题 “Same Tree” 的解法。这就是典型的“双重递归”结构外层递归负责在s上搜索所有可能的根节点内层递归负责以某个根节点为起点做全量比较。仓库源码解读isSubtree 与 isSameTree 的实现仓库中的核心实现位于 572. Subtree of Another Tree.go完整代码如下package leetcode import ( github.com/halfrost/LeetCode-Go/structures ) // TreeNode define type TreeNode structures.TreeNode /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func isSubtree(s *TreeNode, t *TreeNode) bool { if isSameTree(s, t) { return true } if s nil { return false } if isSubtree(s.Left, t) || isSubtree(s.Right, t) { return true } return false } // this is 100 solution func isSameTree(p *TreeNode, q *TreeNode) bool { if p nil q nil { return true } else if p ! nil q ! nil { if p.Val ! q.Val { return false } return isSameTree(p.Left, q.Left) isSameTree(p.Right, q.Right) } else { return false } }isSubtree外层搜索func isSubtree(s *TreeNode, t *TreeNode) bool { if isSameTree(s, t) { return true } if s nil { return false } if isSubtree(s.Left, t) || isSubtree(s.Right, t) { return true } return false }执行顺序逐行拆解先判断isSameTree(s, t)若两棵树根节点相同直接返回true。这一步覆盖了“s 自身就是 t 的子树”的情形也覆盖了任意一个根节点匹配成功的场景if s nil兜底当s已经走到空节点而尚未匹配成功时返回false终止这一分支的递归。注意这个判断放在isSameTree之后原因是isSameTree(nil, nil)本身返回true两棵空树视为相同不能提前拦截而一旦两棵树不是同时为空s nil意味着不可能再往下生长出与t匹配的子树可以安全剪枝左右分支短路递归isSubtree(s.Left, t) || isSubtree(s.Right, t)利用 Go 逻辑运算符的短路特性——只要左子树中找到了匹配就立即返回true不再进入右子树搜索避免无谓遍历。整个外层递归实质上是对s做了一次先序性质的遍历每到达一个节点就尝试用isSameTree对该节点“对齐”t然后继续下探左右子树。isSameTree内层全等判定// this is 100 solution func isSameTree(p *TreeNode, q *TreeNode) bool { if p nil q nil { return true } else if p ! nil q ! nil { if p.Val ! q.Val { return false } return isSameTree(p.Left, q.Left) isSameTree(p.Right, q.Right) } else { return false } }这段代码与仓库中 100. Same Tree.go 的实现完全一致源码注释// this is 100 solution也直接点明了这一关系它把所有情形收敛为三类两棵都为空true两棵都不为空先比较Val值不等立即false否则递归比较左子树与右子树两边同时相等才算相同一棵为空一棵非空false这是结构不一致的直接证据。递归出口清晰、无歧义任何两棵树的比较最终都会落到叶子节点之下的nil上结束。数据结构支撑structures 包中的 TreeNode代码开头的type TreeNode structures.TreeNode是一个类型别名把仓库统一封装的二叉树节点结构引入当前包。该结构定义在 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode } // NULL 方便添加测试数据 var NULL -1 63NULL常量-1 63即 int64 最小值用于在数组表示法中标记空节点配合Ints2TreeNode可以把层序遍历形式的[]int快速还原成一棵真实的二叉树。这一点在测试环节非常重要——测试代码正是用这种数组表示法构造s和t的。仓库根目录的 go.mod 通过replace github.com/halfrost/LeetCode-Go/structures ./structures将structures子模块指向本地目录因此无论是跑测试还是做二次开发import github.com/halfrost/LeetCode-Go/structures都会直接解析到当前仓库的 structures 目录无需额外拉取远程依赖。测试用例验证表驱动测试与数组建树测试文件 572. Subtree of Another Tree_test.go 采用仓库统一的**表驱动table-driven**测试风格先定义question572结构体装载“参数 期望答案”再遍历用例逐一断言。核心用例包括输入 s层序数组输入 t层序数组期望结果[][]true两棵空树[3,4,5,1,2][4,1,2]true题目示例 1[1,1][1]true根节点值相同即命中深层链式结构[1,null,1,null,...,2]对应链式结构[1,null,1,null,...,2]true长链场景[3,4,5,1,2][3,1,2]false值相同但结构不同其中前两个用例与题目给出的示例直接对应第三个用例s[1,1]、t[1]验证“节点值相同即子树成立”最后一个用例s[3,4,5,1,2]、t[3,1,2]则验证了“根节点值相等都是 3但子树结构不匹配”必须返回false——这恰好击中了内层isSameTree中“值相等后还要递归比较左右子树”的关键分支。测试的建树方式如下roots : structures.Ints2TreeNode(p.s) roott : structures.Ints2TreeNode(p.t) got : isSubtree(roots, roott)Ints2TreeNode在 structures/TreeNode.go 中实现它把数组首元素作为根用一个队列按层序遍历顺序依次挂接左右孩子遇到值为NULL的位置则跳过挂接。这样测试用例可以用极其紧凑的数组形式描述任意复杂的树包括用例 4 那种深度可达数十层的退化链。复杂度分析设s的节点数为mt的节点数为n。时间复杂度外层isSubtree在最坏情况下要对s的每个节点调用一次isSameTree每次比较最坏需要遍历整棵t因此最坏为O(m·n)。典型场景是s退化为链表、每个节点都与t的根值相同但比较到底才失败空间复杂度两处递归的深度分别受s和t的高度约束最坏链式树情况下为O(max(hs, ht))其中hs、ht分别为两棵树的高度平衡树场景下则退化为 O(log m log n)。这也是该解法在 LeetCode 上“中等难度”定位的体现思路直观、编码量小但面对退化输入时复杂度较高适合作为理解“双重递归”的入门题。从源码结构可以推断的扩展方向基于本仓库的实现可以顺带指出两种常见优化思路仓库当前未收录属于延伸探讨先序遍历序列化 字符串匹配将两棵树序列化为带空节点标记如#的先序字符串则“子树”判定转化为“字符串子串”判定可用 KMP 等算法把时间降到 O(m n)但需要注意序列化格式必须能唯一重建二叉树如1,#,2,#,#形式哈希化整棵子树为树的每个节点计算以其为根的子树哈希值先哈希后比较多数场景下可将平均复杂度降到接近线性但需要小心哈希冲突与构造攻击。需要说明的是以上两点属于算法社区的常见延伸并非当前仓库 572. Subtree of Another Tree.go 中的实现内容。本地运行与验证仓库是只读的你可以在本地克隆或直接打开本项目后进入题解目录运行测试验证本题实现# 克隆项目如需 git clone https://gitcode.com/GitHub_Trending/le/LeetCode-Go.git # 进入题解目录运行本题测试 cd LeetCode-Go go test -v ./leetcode/0572.Subtree-of-Another-Tree/ -run Test_Problem572其中Test_Problem572是 572. Subtree of Another Tree_test.go 中定义的测试函数名-run指定只执行本题用例。若需验证全部题解可在仓库根目录执行go test ./...仓库根目录的 gotest.sh 也提供了批量测试脚本的参考写法。由于 go.mod 已通过replace指令把structures子模块指向本地路径测试可以直接基于 structures 目录编译无需网络下载。小结核心结论t是s的子树当且仅当存在s的某个节点使得以该节点为根的整棵子树与t完全同构s自身也是自己的子树算法骨架外层isSubtree遍历s的每个节点内层isSameTree即第 100 题原题解法做全等比较两者都是经典递归仓库验证572. Subtree of Another Tree.go 提供实现572. Subtree of Another Tree_test.go 覆盖空树、示例、深层链、结构不匹配等多类用例可在本地直接运行验证复杂度边界最坏 O(m·n) 的时间与 O(max(hs, ht)) 的空间适合作为双重递归思想的入门范本也值得在面试中顺带讨论序列化 KMP 或子树哈希等优化。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考