CS-Notes 剑指 Offer 第 26 题详解：用两段递归类函数实现二叉树子结构匹配

CS-Notes 剑指 Offer 第 26 题详解用两段递归类函数实现二叉树子结构匹配【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 仓库中 剑指 Offer 题解 - 树的子结构 一文展开完整继承其题目描述与官方解法代码并结合该仓库其他树类题解如 二叉树的镜像、对称的二叉树中的同构递归套路深入剖析“子结构判定”的两段式递归设计、空树边界的语义约定以及复杂度与易错点帮助读者掌握二叉树模式匹配类面试题的标准解法与变形思路。题目描述剑指 Offer 第 26 题“树的子结构”的原始定义如下输入两棵二叉树 A 和 B判断 B 是不是 A 的子结构。约定空树不是任意树的子结构即空树不算作 A 的子结构。直观示例如下图所示树root2右图是否是树root1左图的子结构。在《剑指 Offer》的解题约定中“B 是 A 的子结构”需要满足一个结构性条件存在 A 中的某个节点 N使得以 N 为根的子树与 B 的结构一致对应节点值相等且 B 中不存在的子节点不影响判定——也就是说匹配只要求 B 中已有的节点在 A 的对应位置上找到值相等的节点B 中为空的分支不要求 A 中也为空。这一约定是理解后续代码中所有终止条件的关键。核心思路全局搜索 局部验证的两段式递归子结构判定天然可以拆解为两个相互递归的子问题这也是该题解法代码中两个函数的分工全局搜索HasSubtree以root1的每一个节点为候选起点尝试让root2从该节点开始匹配。若当前节点匹配成功则返回 true否则依次退回其左子树、右子树继续搜索局部验证isSubtreeWithRoot假设两棵树的当前根节点已经对齐逐层向下验证“以root2当前节点为根的结构是否完全被root1对应位置覆盖”。两者形成经典的“外层遍历候选根、内层验证匹配”模式与 对称的二叉树 中“双指针同步下探两棵树”、二叉树的镜像 中“前序递归交换”属于同一族“对两棵或同一棵的树做同步递归”的套路。完整解法代码与逐行解析以下代码完整来自仓库原文档 26. 树的子结构是牛客网在线判题环境下的标准 Java 实现public boolean HasSubtree(TreeNode root1, TreeNode root2) { if (root1 null || root2 null) return false; return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) { if (root2 null) return true; if (root1 null) return false; if (root1.val ! root2.val) return false; return isSubtreeWithRoot(root1.left, root2.left) isSubtreeWithRoot(root1.right, root2.right); }逐行说明入口防御root1 null || root2 null时直接返回 false。root1为空说明没有候选起点自然不存在子结构root2为空时此实现也返回 false等价于采用了“空树不是任意树子结构”的判题口径见下一节对两种约定的讨论。短路求值的候选遍历isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2)一行完成了“先验证当前根、再向左右子树扩散”的全局搜索。||的短路特性保证一旦某个起点验证成功后续子树不再被访问平均情况下可以提前退出。内层验证的三种终止root2 null返回 true表示root2的结构已经全部匹配完毕剩下root1侧多出的节点不影响结论——这正是“子结构”区别于“两棵树完全相同”的语义所在root1 null返回 falseroot2还有剩余结构但root1侧已经没有节点可对应验证失败节点值不等返回 false结构对齐的前提是值相等一旦不等立即剪枝递归下探值相等时同时递归左右两侧任何一侧失败即整体失败与 对称的二叉树 中isSymmetrical(t1.left, t2.right) isSymmetrical(t1.right, t2.left)的同步下探写法结构一致。空树语义约定为什么两处空判断“一真一假”读这段代码时最容易产生疑问的是同为遇到空节点HasSubtree里root2 null返回 false而isSubtreeWithRoot里root2 null却返回 true。这两处并不矛盾而是分别服务于不同的判定时机入口处HasSubtree第一行root2作为整体输入就是空树。按《剑指 Offer》的题目约定空树不被认为是任何树的子结构因此直接拒绝避免把“空对非空”误判为成功验证过程中isSubtreeWithRoot第一行root2是在递归下探途中“用完了”即它的剩余部分已经与root1的某个子树逐节点匹配完毕返回 true 是“匹配完成”的正常收尾而不是“空树等于任意树”。这种组合使代码同时兼容两种常见判题口径若采用《剑指 Offer》2019 版/LeetCode 572 风格空树不算子结构入口的root2 null分支已经兜底若采用“空树是任意树子结构”的宽松定义只需将入口处的root2 null改为返回 true 即可内层验证逻辑保持不变。理解这一点对后续应对面试官追问“空树怎么处理”至关重要。复杂度分析设root1的节点数为 Mroot2的节点数为 N时间复杂度最坏情况下root1的每个节点都会触发一次对root2的完整结构验证例如所有节点值都相同、直到深处才出现结构差异总代价为 O(M×N)由于短路求值平均情况下实际访问的节点对远小于 M×N空间复杂度仅来自递归调用栈外层搜索深度最深 M 层内层验证深度最深 N 层合计 O(M N)。对于面试中更常见的中等规模输入该递归解法已经足够题目本身也未要求优化到线性级别重点在于把递归边界讲清楚。边界与易错点清单root2只有一侧子树如root2根节点只有左孩子验证root1对应节点时其右孩子可以为空也可以非空内层递归对root2.right null直接返回 true这是“子结构”而非“相等子树”的直接体现值相等但结构不同isSubtreeWithRoot会因在第一个结构不匹配的分支立刻返回 false不会继续浪费搜索单节点树root1、root2都只有一个节点且值相等时两侧递归均在root2 null处返回 true结果为 true值不等则入口比较即失败常见写法错误把内层验证的root2 null误写为 false、或忘记入口对root1 null的防御虽然isSubtreeWithRoot能处理root1为空但入口提前剪枝可避免一次无意义的调用。与同类题的关系及延伸若把判定条件从“子结构”收紧为“完全相同的子树”则只需将isSubtreeWithRoot中root2 null的返回值由 true 改为root1 null其余搜索框架不变即得到 LeetCode 572“另一棵树的子树”的判定方式该题不认为空树是子树入口对root2 null返回 false 与其口径一致若 B 是有序序列而 A 是二叉树则演变为“验证前序/后序序列是否对应树结构”一类问题可参考仓库中 7. 重建二叉树 对“遍历序列与树结构互推”的分析递归同步下探两棵树的模板还出现在 28. 对称的二叉树对称即“左子树与右子树互为镜像”中掌握本节两段式结构后这类题基本是同构替换更多二叉树面试题层序打印、路径和等可在 剑指 Offer 题解 - 目录 的“树”分类下按题号继续学习。小结树的子结构一题的精髓在于把“匹配”与“搜索”拆成两个递归函数外层HasSubtree负责在root1上枚举所有候选根并借助短路求值提前退出内层isSubtreeWithRoot负责在根对齐的前提下逐节点验证并用root2 null → true表达“结构已匹配完整”的语义。理解入口空树防御与验证过程空树收尾这两处空判断的分工是该题答到面试官点头的关键再结合 O(M×N) 最坏时间的复杂度说明即可完成一次完整而严谨的作答。【免费下载链接】CS-Notes:books: 技术面试必备基础知识、Leetcode、计算机操作系统、计算机网络、系统设计项目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考