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

剑指offer——JZ26 树的子结构 解题思路与具体代码【C++】

一、题目描述与要求

树的子结构_牛客题霸_牛客网 (nowcoder.com)

题目描述

输入两棵二叉树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


二、解题思路

根据题目描述,我们需要判断B树是否为A树的子树。

首先题目规定了“空树不是任意一个树的子结构”,所以我们先判断B树是否为空树,是的话直接返回false;

然后如果A是空树且B不是空树的话,那么B肯定不是A的子树,也返回false;

但是如果A和B都为空或者A不为空B为空的情况下,则B就是A的子树,返回true;(这里的空,可应该解释为空节点)

若A树B树都不为空,则我们就需要对两个树进行遍历,然后比较,我们想要判断B树是否为A树的子树,那就需要从根结点开始,以每个结点为“根结点”然后跟B树进行比较。【这是因为B树不一定是从A的根结点开始的,所以在当前结点不符合的情况下,我们依次将左节点与右节点作为“根结点”与B树进行比较】

如果根结点的值相同,则去判断左子树与右子树是否相同,都相同就代表B是A的子树,只要有不同则就需要我们继续往下找,也就是换一个结点为“根结点”,然后与B树继续比较。

直至找到与B树相同的结点或者A树遍历结束。

最后对所设置的三个标志进行判断。flag1是指以根结点开始与B树比较的结果,flag2是指以左子树的结点为开始与B树比较的结果,flag3是指以右子树的结点为开始与B树比较的结果。三者只需要有一个为真就代表B树是A的子树。【每个比较都是递归的,都是以当前节点为根结点,以此去访问左子树与右子树】


三、具体代码

class Solution {
public:bool recursion(TreeNode* pRoot1,TreeNode* pRoot2){//当一个节点存在另一个不存在时if(pRoot1==nullptr&&pRoot2!=nullptr) return false;//两个都为空则返回trueif(pRoot1==nullptr||pRoot2==nullptr) return true;//比较节点值if(pRoot1->val!=pRoot2->val) return false;//递归比较子树return recursion(pRoot1->left,pRoot2->left) && recursion(pRoot1->right,pRoot2->right);}bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {//B为空树if(pRoot2==nullptr)  return false;//A为空,B不为空if(pRoot1==nullptr&&pRoot2!=nullptr) return false;//A不为空B为空 A,B都为空 if(pRoot1==nullptr||pRoot2==nullptr) return true;//把当前根结点的二叉树与B树进行递归比较bool flag1=recursion(pRoot1,pRoot2);//递归A树的每个结点 分别以每个结点为根结点进行比较bool flag2=HasSubtree(pRoot1->left,pRoot2);bool flag3=HasSubtree(pRoot1->right, pRoot2);return flag1||flag2||flag3;}
};

http://www.lryc.cn/news/183504.html

相关文章:

  • NEFU数字图像处理(1)绪论
  • 数值分析学习笔记——绪论【华科B站教程版本】
  • 节日灯饰灯串灯出口欧洲CE认证办理
  • 一线大厂Redis高并发缓存架构实战与性能优化
  • PHP 行事准则:allow_url_fopen 与 allow_url_include
  • Replicate + ngrok云端大模型API实现教程
  • 蓝桥等考Python组别十四级005
  • Linux 本地 Docker Registry本地镜像仓库远程连接
  • 二十九、高级IO与多路转接之epollreactor(收官!)
  • vite dev开发模式下支持外部模块引用
  • Chrome出现STATUS_STACK_BUFFER_OVERRUN解决方法之一
  • 【JavaEE】JavaScript
  • 剑指offer——JZ7 重建二叉树 解题思路与具体代码【C++】
  • 图片批量编辑器,轻松拼接多张图片,创意无限!
  • 蓝桥等考Python组别十四级008
  • 【linux进程(二)】如何创建子进程?--fork函数深度剖析
  • 数字IC前端学习笔记:数字乘法器的优化设计(华莱士树乘法器)
  • CountDownLatch 批量更改使用,
  • 910数据结构(2019年真题)
  • 推荐系统实践 笔记
  • 【JavaEE】JUC(Java.util.concurrent)常见类
  • 清除浮动的方法
  • LangChain 摘要 和问答示例
  • (32)测距仪(声纳、激光雷达、深度摄影机)
  • 教你拥有一个自己的QQ机器人!0基础超详细保姆级教学!基于NoneBot2 Windows端搭建QQ机器人
  • 智能银行卡明细筛选与统计,轻松掌握账户总花销!
  • SRT服务器SLS
  • Linux 安装 Android SDK
  • 【QT开发笔记-基础篇】| 第四章 事件QEvent | 4.4 鼠标按下、移动、释放事件
  • vue3父子通信+ref,toRef,toRefs使用实例