当前位置: 首页 > 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;}
};

相关文章:

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

一、题目描述与要求 树的子结构_牛客题霸_牛客网 (nowcoder.com) 题目描述 输入两棵二叉树A&#xff0c;B&#xff0c;判断B是不是A的子结构。&#xff08;我们约定空树不是任意一个树的子结构&#xff09; 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}&#xff0c;B为{8,9,2}&…...

NEFU数字图像处理(1)绪论

一、简介 1.1什么是数字图像 图像是三维场景在二维平面上的影像。根据其存储方式和表现形式&#xff0c;可以将图像分为模拟图像和数字图像两大类 图像处理方法&#xff1a;光学方法、电子学方法 模拟图像&#xff1a;连续的图像数字图像&#xff1a;通过对时间上和数值上连续…...

数值分析学习笔记——绪论【华科B站教程版本】

绪论 数值分析概念 用计算机求解数学问题的数值方法和理论 三大科学研究方法 实验理论分析科学计算&#xff08;用计算机去辅助研究&#xff09;&#xff1a;数值方法计算机 解析解和近似解 解析解&#xff1a;使用数学方法求出或推导出的结果&#xff0c;往往可以求解出…...

节日灯饰灯串灯出口欧洲CE认证办理

灯串&#xff08;灯带&#xff09;&#xff0c;这个产品的形状就象一根带子一样&#xff0c;再加上产品的主要原件就是LED&#xff0c;因此叫做灯串或者灯带。2022年&#xff0c;我国灯具及相关配件产品出口总额超过460亿美元。其中北美是最大的出口市场。其次是欧洲市场&#…...

一线大厂Redis高并发缓存架构实战与性能优化

文章目录 一、redis主从架构锁失效问题分析二、从CAP角度剖析redis与zookeeper分布式锁区别三、redlock分布式锁原理与存在的问题分析四、大促场景如何将分布式锁性能提升100倍五、高并发redis架构代码实战 一、redis主从架构锁失效问题分析 我们都知道&#xff0c;一般的互联…...

PHP 行事准则:allow_url_fopen 与 allow_url_include

文章目录 参考环境allow_url_fopenallow_url_fopen 配置项操作远程文件file 协议 allow_url_includeallow_url_include 配置项 allow_url_include 与 allow_url_fopen区别联系默认配置配置项关闭所导致异常运行时配置ini_set()限制 参考 项目描述搜索引擎Bing、GoogleAI 大模型…...

Replicate + ngrok云端大模型API实现教程

ChatGPT 的诞生预示着人工智能和机器学习领域的新时代。 日新月异&#xff0c;Hugging Face 不断推出突破性的语言模型&#xff0c;重新定义人机交互的界限。欢迎来到未来&#xff01; 当然&#xff0c;有很多选项可以对它们进行推断。在本文中&#xff0c;我将告诉大家如何使…...

蓝桥等考Python组别十四级005

蓝桥等考Python组别十四级 第一部分:选择题 1、Python L14 (15分) 运行下面程序,输出的结果是( )。 d = {1 : one, 2 : two, 3 : three, 4 : four} print(d[2]) onetwothreefour正确答案:B...

Linux 本地 Docker Registry本地镜像仓库远程连接

Linux 本地 Docker Registry本地镜像仓库远程连接 Docker Registry 本地镜像仓库,简单几步结合cpolar内网穿透工具实现远程pull or push (拉取和推送)镜像,不受本地局域网限制&#xff01; 1. 部署Docker Registry 使用官网安装方式,docker命令一键启动,该命令启动一个regis…...

二十九、高级IO与多路转接之epollreactor(收官!)

文章目录 一、Poll&#xff08;一&#xff09;定义&#xff08;二&#xff09;实现原理&#xff08;三&#xff09;优点&#xff08;四&#xff09;缺点 二、I/O多路转接之epoll&#xff08;一&#xff09;从网卡接收数据说起&#xff08;二&#xff09;如何知道接收了数据&…...

vite dev开发模式下支持外部模块引用

web工程中经常需要使用外部的cdn资源&#xff0c;比如lodash、three.js等&#xff1a; <script type"importmap">{"imports": {"lodash": "https://unpkg.com/lodash-es4.17.21/lodash.js"}} </script> vite build通过r…...

Chrome出现STATUS_STACK_BUFFER_OVERRUN解决方法之一

Chrome出现STATUS_STACK_BUFFER_OVERRUN错误代码&#xff0c;setting都无法打开 解决方法1&#xff1a;兼容性设置为win7 解决方法2&#xff1a; 1&#xff0c;开始菜单搜索Exploit Protection 2&#xff0c;添加程序进行自定义&#xff0c;点号&#xff0c;按程序名称添加 …...

【JavaEE】JavaScript

JavaScript 文章目录 JavaScript组成书写方式行内式内嵌式外部式&#xff08;推荐写法&#xff09; 输入输出变量创建动态类型基本数据类型数字类型特殊数字值 String转义字符求长度字符串拼接布尔类型undefined未定义数据类型null 运算符条件语句if语句三元表达式switch 循环语…...

剑指offer——JZ7 重建二叉树 解题思路与具体代码【C++】

一、题目描述与要求 重建二叉树_牛客题霸_牛客网 (nowcoder.com) 题目描述 给定节点数为 n 的二叉树的前序遍历和中序遍历结果&#xff0c;请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}&#xff0c;则重建出…...

图片批量编辑器,轻松拼接多张图片,创意无限!

你是否曾经遇到这样的问题&#xff1a;需要将多张图片拼接成一张完整的画面&#xff0c;却缺乏专业的图片编辑技能&#xff1f;现在&#xff0c;我们为你带来一款强大的图片批量编辑器——让你轻松实现多张图片拼接&#xff0c;创意无限&#xff01; 这款图片批量编辑器可以帮助…...

蓝桥等考Python组别十四级008

第一部分:选择题 1、Python L14 (15分) 运行下面程序,输出的结果是( )。 d = {1: "red", 2: "yellow", 3: "blue", 4: "green"} print(d[2]) redyellowbluegreen正确答案:B 2、Python L14 (...

【linux进程(二)】如何创建子进程?--fork函数深度剖析

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:Linux从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学更多操作系统知识   &#x1f51d;&#x1f51d; 进程状态管理 1. 前言2. 查看…...

数字IC前端学习笔记:数字乘法器的优化设计(华莱士树乘法器)

相关阅读 数字IC前端https://blog.csdn.net/weixin_45791458/category_12173698.html?spm1001.2014.3001.5482 进位保留乘法器依旧保留着阵列的排列规则&#xff0c;只是进位是沿斜下角&#xff0c;如果能使用树形结构来规划这些进位保留加法器&#xff0c;就能获得更短的关键…...

CountDownLatch 批量更改使用,

代码 import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper; import com.baomidou.mybatisplus.extension.service.impl.ServiceImpl; import com.first.pet.platform.entity.PlatformAddress; import com.first.pet.platform.mapper.PlatformAddressMapper; …...

910数据结构(2019年真题)

算法设计题 问题1 有一种排序算法叫做计数排序。这种排序算法对一个待排序的表(采用顺序存储)进行排序,并将排序结果存放到另一个新的表中。必须注意的是,表中所有待排序的关键字互不相同,计数排序算法针对表中的每个元素,扫描待排序的表一趟,统计表中有多少个元素的关…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...