LeetCode-Book《剑指 Offer 26. 树的子结构》：isSubStructure 与 recur 两级递归判定的完整解析

LeetCode-Book《剑指 Offer 26. 树的子结构》isSubStructure 与 recur 两级递归判定的完整解析【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文基于 LeetCode-Book 仓库中《剑指 Offer 26. 树的子结构》的题解文档系统讲解判断树 B 是否是树 A 的子结构这一经典二叉树递归问题先通过先序遍历在树 A 中定位候选根节点再借助一个独立的匹配递归逐一比对左右子树。读完后你将掌握isSubStructure(A, B)与recur(A, B)两个函数各自的职责边界、三个终止条件的判定顺序以及 Python / Java / C 三种语言下可直接运行的完整实现含仓库中的测试用例与验证结果。一、问题建模子结构判定拆成定位 匹配两步若树B是树A的子结构则子结构的根节点可能是树A中的任意一个节点。因此判断树B是否是树A的子结构需要完成以下两步工作先序遍历树A中的每个节点 $n_A$对应函数isSubStructure(A, B)判断树A中以 $n_A$ 为根节点的子树是否包含树B对应函数recur(A, B)。这个外层找根、内层匹配的分工是整个算法的核心isSubStructure负责广度上的定位——它不关心从哪个位置开始比对而是遍历树 A 的每一个节点尝试以其为起点recur负责深度上的比对——一旦确定了候选根它就只沿着两棵树的同侧子树左对左、右对右做严格的结构匹配不做任何回溯或换位置。名词规定树A的根节点记作节点A树B的根节点称为节点B。二、recur(A, B)函数单起点匹配的终止条件与返回值recur从某一对候选节点出发判断A 的这棵子树是否覆盖 B 的这棵子树。终止条件按判定顺序当节点B为空说明树B已匹配完成越过叶子节点返回 $true$当节点A为空说明已经越过树A的叶节点即匹配失败返回 $false$当节点A和B的值不同说明匹配失败返回 $false$。注意终止条件的书写顺序是有讲究的先判B是否为空再判A是否为空。因为B 为空即成功、A 为空即失败若反过来写当A先为空时B恰好也空的情况双空叶子会被误判为失败。返回值通过了全部终止条件即A非空且A.val B.val后递归比对两侧子树判断A和B的左子节点是否相等即recur(A.left, B.left)判断A和B的右子节点是否相等即recur(A.right, B.right)两者必须同时成立用and/连接。这与isSubStructure中层级之间用or连接形成鲜明对比匹配是与结构必须完整覆盖定位是或任意一个位置命中即可。三、isSubStructure(A, B)函数先序遍历驱动的全局判定特例处理当树A为空或树B为空时直接返回 $false$。这一点是题目约定的直接体现空树B不被认为构成任何树A的子结构因此即使recur中B 为空返回 true入口函数仍要把B为空的情况挡在外面。返回值三个条件的或若树B是树A的子结构则必满足以下三种情况之一因此用或||连接以节点A为根节点的子树包含树B对应recur(A, B)树B是树A左子树的子结构对应isSubStructure(A.left, B)树B是树A右子树的子结构对应isSubStructure(A.right, B)。其中第 2、3 两条实质上是在对树A做先序遍历——递归地把子结构判定问题缩小到左右两棵子树上配合短路求值||前一项为真则不再执行后项一旦在某个节点匹配成功立即返回无需遍历剩余节点。四、三语言参考实现仓库为本题提供了 Python、Java、C 三个版本的实现方案编号 s1三者算法完全一致。Pythonsfo_26_substructure_of_a_binary_tree_s1.py 中的解法class Solution: def isSubStructure(self, A: TreeNode, B: TreeNode) - bool: def recur(A, B): if not B: return True if not A or A.val ! B.val: return False return recur(A.left, B.left) and recur(A.right, B.right) return bool(A and B) and ( recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) )注意 Python 版入口处的bool(A and B)这是为了与 Java/C 中(A ! null B ! null) 的语义对齐——and在 Python 中返回的是最后一个被求值的操作数本身而非布尔值bool(...)保证了函数返回类型是bool同时借助and的短路特性实现A、B 均非空的守卫条件。recur则以闭包形式内嵌于isSubStructure避免了将其挂为成员函数带来的额外属性查找。Javasfo_26_substructure_of_a_binary_tree_s1.java 中的解法class Solution { public boolean isSubStructure(TreeNode A, TreeNode B) { return (A ! null B ! null) (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); } boolean recur(TreeNode A, TreeNode B) { if (B null) return true; if (A null || A.val ! B.val) return false; return recur(A.left, B.left) recur(A.right, B.right); } }Java 版依赖的短路求值完成空值守卫只要A或B为null整个表达式立即返回false后面的三个分支根本不会被执行。Csfo_26_substructure_of_a_binary_tree_s1.cpp 中的解法class Solution { public: bool isSubStructure(TreeNode* A, TreeNode* B) { return (A ! nullptr B ! nullptr) (recur(A, B) || isSubStructure(A-left, B) || isSubStructure(A-right, B)); } private: bool recur(TreeNode* A, TreeNode* B) { if (B nullptr) return true; if (A nullptr || A-val ! B-val) return false; return recur(A-left, B-left) recur(A-right, B-right); } };C 版与 Java 版结构一致差异在于使用nullptr判空、-指针访问且recur声明为private私有辅助函数仅暴露isSubStructure公共接口。五、测试用例与运行验证三个语言版本的驱动代码都使用了同一组测试用例直观展示了题目定义的结构A: B: 3 4 / \ / 4 5 1 / \ 1 2即树A由层序序列[3, 4, 5, 1, 2, ...]构建空位占位符Python 用NoneC 用INT_MAX树B由[4, 1, ...]构建。树B4 带左子节点 1恰好是树A中以节点 4 为根的子树期望输出True。以仓库中的 Python 版本为例实际运行 sfo_26_substructure_of_a_binary_tree_s1.py$ python3 sfo_26_substructure_of_a_binary_tree_s1.py True输出与预期一致验证了两级递归逻辑的正确性。构建这些测试树所用的节点定义与工具函数分别位于各语言的include目录中例如 C 的 TreeNode.hpp 定义了TreeNode结构体val、left、right三个成员以及按层序向量建树的vectorToTree函数Java 的arrToTree、Python 的list_to_tree与之对应。六、复杂度分析时间复杂度 $O(MN)$其中 $M, N$ 分别为树A和树B的节点数量。最坏情况下先序遍历树A占用 $O(M)$每次调用recur(A, B)判断占用 $O(N)$两者相乘得 $O(MN)$。若借助短路求值实际平均开销会低于该上界。空间复杂度 $O(M)$即递归调用栈的最大深度。当树A和树B都退化为链表单侧链时递归调用深度最大。当 $M \leq N$ 时遍历树A与递归判断的总递归深度为 $M$当 $M N$ 时最差情况为遍历至树A的叶节点此时总递归深度仍为 $M$。七、关键要点回顾两个函数各司其职isSubStructure用或连接三种情况实现在树 A 上的先序遍历与定位recur用与连接左右两侧递归实现单起点下的严格结构匹配。混淆这两者的布尔连接符是本题最常见的实现错误。终止条件顺序不可颠倒recur中先判B为空匹配完成再判A为空匹配失败最后判值相等入口函数再单独拦截A 或 B 为空返回 false的特例。短路求值是免费的优化||与的短路特性使匹配成功后立即停止遍历使平均时间低于 $O(MN)$ 的最坏上界。三语言实现一一对应Python 闭包版、Java 成员函数版、C 私有函数版在语义上完全等价可直接作为面试白板代码的模板完整源码见 Python 实现、Java 实现、C 实现。本文内容承接自 剑指 Offer 26. 树的子结构 的题解结合仓库中三语言代码的实际测试用例与运行结果进行了验证和扩充。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考