算法的学习笔记—树的子结构（牛客JZ26）

😀前言
在算法面试中，二叉树相关的问题经常出现，其中一个经典的问题是判断一棵二叉树B是否是另一棵二叉树A的子结构。本文将深入探讨这个问题，并通过代码示例展示如何解决这一问题。

🏠个人主页：尘觉主页

😊树的子结构

🤗题目链接

牛客网

😆问题描述

我们有两棵二叉树A和B，要求判断B是否是A的子结构。需要注意的是，题目明确规定了空树不是任何树的子结构。

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

🤔示例

• 示例1：

  输入：A = {8,8,7,9,2,#,#,#,#,4,7}，B = {8,9,2}

  输出：true

• 示例2：

  输入：A = {1,2,3,4,5}，B = {2,4}

  输出：true

• 示例3：

  输入：A = {1,2,3}，B = {3,1}

  输出：false

数据范围

• 0 ≤ A的节点个数 ≤ 10000
• 0 ≤ B的节点个数 ≤ 10000

😋解题思路

要判断B是否为A的子结构，我们可以采用递归的方法。具体步骤如下：

1. 判断当前节点是否匹配：
   • 从二叉树A的根节点开始，判断当前节点是否与树B的根节点相同。
   • 如果相同，进一步递归判断左右子树是否都匹配。
2. 递归搜索整棵树：
   • 即使当前节点与树B的根节点不匹配，我们仍需递归检查A的左右子树，继续寻找可能的匹配子结构。
3. 终止条件：
   • 如果树B的所有节点都匹配，返回true。
   • 如果树A已经遍历完且没有找到匹配，返回false。

💖Java实现

以下是该问题的Java实现代码：

public class Solution {// 主函数，判断B是否为A的子结构public boolean HasSubtree(TreeNode root1, TreeNode root2) {// 如果A或B为空，直接返回falseif (root1 == null || root2 == null)return false;// 检查当前节点，或递归检查左右子树return isSubtreeWithRoot(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);}// 辅助函数，判断以root1为根的树是否包含以root2为根的子结构private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {// 如果B已经遍历完，说明匹配成功if (root2 == null)return true;// 如果A先遍历完，或者当前节点不匹配，返回falseif (root1 == null || root1.val != root2.val)return false;// 递归检查左右子树return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);}
}

💖代码解析

1. HasSubtree方法：
   • 这是主函数。首先检查A和B是否为空树。如果是，返回false。否则，调用辅助函数isSubtreeWithRoot判断当前根节点是否匹配，同时递归检查A的左右子树。
2. isSubtreeWithRoot方法：
   • 这是一个递归函数，用于检查以root1为根的子树是否包含以root2为根的子结构。首先判断root2是否已经遍历完，如果是，返回true。如果root1为空或当前节点的值不相等，返回false。否则，递归检查左右子树是否匹配。

😄总结

这个问题通过递归的方式遍历二叉树，逐步检查是否存在匹配的子结构。尽管递归的方式看似复杂，但它能有效地解决类似问题。理解了这个问题的递归思路，对于二叉树相关的其他问题也会有很大帮助。

希望通过这篇文章，您对二叉树子结构的判断有了更清晰的认识和理解。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞