当前位置: 首页 > news >正文

牛客网剑指Offer-树篇-JZ26 树的子结构

题目

来源:JZ26 树的子结构
描述
输入两棵二叉树A,B,判断B是不是A的子结构。(我们约定空树不是任意一个树的子结构)
假如给定A为{8,8,7,9,2,#,#,#,#,4,7},B为{8,9,2},2个树的结构如下,可以看出B是A的子结构
在这里插入图片描述

数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
示例1
输入:
{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值:
true
示例2
输入:
{1,2,3,4,5},{2,4}
返回值:
true
示例3
输入:
{1,2,3},{3,1}
返回值:
false

解析

官方题解讲得一塌糊涂,关键概念没解释就算了,代码逻辑还非常混乱。这题的难度应该算较难而不是中等,因为有个关键点很难想到。假设两棵树分别为A,B,B为子树,则B为A的子树有如下三种情况:
1.B和A的根节点相同,B为A的子树。
2.B和A的根节点不同,B为A的左子树的子树。
3.B和A的根节点不同,B为A的右子树的子树。
显然,这三种情况都需要递归,但因为第一种情况和后两种是有本质区别的,所以第一种情况就需要单独写一个函数来判断,假设为IsSubtree。由于题目规定空树不是任意树的子树,所以HasSubtree开头就要排除B为空的情况,则这会引入一个关键点:IsSubtree中传入的B树的节点如果为空,则当前的IsSubtree的递归层数至少是两层,该B树节点不可能在第一层,而且前几层一定都是匹配成功的,所以一定要返回true。 下面举例说明:
在这里插入图片描述

显然,当递归层中的B树节点为空时,前几层的节点是匹配成功的,所以要返回true。图中总共要处理两次B树节点为空的情况,两次都要返回true,B树才能正确匹配A树。这点确实是比较难的,这点想不到,这题就不可能做对。
关键点解决了,IsSubtree的算法就不难写了:
1.判断B树节点是否空,若空则返回true。
2.判断A树节点是否为空,若空则返回false。
3.此时A树节点和B树节点都不空,判断它们的值是否相等,若不相等则返回false。
4.此时A树节点和B树节点都不空且相等,则递归判断它们的左右子树是否也都相等。
IsSubtree的实现如下:

bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1->val != pRoot2->val)return false;return IsSubtree(pRoot1->left, pRoot2->left) &&IsSubtree(pRoot1->right, pRoot2->right);
}

这个函数是本题的核心,写对了,后面就很简单了:假设主函数为HasSubtree,则算法如下:
1.判断B树或A树的节点是否空,空则返回false(题目规定空树不是任意树的子树)。
2.调用IsSubtree,判断B和A的根节点是否相同且B是否为A的子树,如果是则返回true。
3.此时B和A的根节点不同,递归判断B是否为A的左(右)子树的子树。
完整代码如下:

bool IsSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot2 ) return true;if (!pRoot1 || pRoot1->val != pRoot2->val)return false;return IsSubtree(pRoot1->left, pRoot2->left) &&IsSubtree(pRoot1->right, pRoot2->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (!pRoot1 || !pRoot2)return false;return IsSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2)|| HasSubtree(pRoot1->right, pRoot2)  ;
}
http://www.lryc.cn/news/473469.html

相关文章:

  • FFmpeg 4.3 音视频-多路H265监控录放C++开发六,使用SDLVSQT显示yuv文件
  • Spring 设计模式之适配器模式
  • 多传感器数字化分析系统
  • Java 基础教学:面向对象编程基础-封装、继承与多态
  • Ubuntu环境本地部署DbGate数据库管理工具并实现无公网IP远程访问
  • 【AI抠图整合包及教程】Meta SAM 2:视觉分割的革命性飞跃
  • 使用语言模型进行文本摘要的五个级别(llm)
  • ubuntu交叉编译libffi库给arm平台使用
  • 【jvm】空间分配担保策略
  • iQOO手机怎样将屏幕投射到MacBook?可以同步音频吗?
  • BUU usualCrypt1
  • 第十七章 标准库特殊设施
  • 【格言分享】程序员的经典名言解读
  • SpringBoot接收LocalDateTime参数
  • Typora配置GitHub图床--结合PicGo
  • 【书生.浦语实战营】——入门岛
  • WPF+MVVM案例实战(十四)- 封装一个自定义消息弹窗控件(下)
  • 嵌入式——STM32外设应用
  • HCIA(ACL)
  • react基础之reactHooks
  • Java基础0-Java概览
  • SW绘制曲面
  • css知识点梳理2
  • 攻防世界 MISC miao~详解
  • 使用 `tracert [options] <目标地址>` 命令的详细介绍
  • 闲一品交易平台:SpringBoot技术的新境界
  • 【深入浅出】深入浅出transformer(附面试题)
  • 苹果重大更新,macOS与iOS同时推出更新!功能真好用
  • 刘艳兵-DBA016-在您的数据库中,SALES表存在于SH用户中,并且启用了统一审计。作为DBA,您成功执行了以下指令:
  • 力扣题目解析--整数反转