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

相关文章:

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

题目 来源&#xff1a;JZ26 树的子结构 描述 输入两棵二叉树A&#xff0c;B&#xff0c;判断B是不是A的子结构。&#xff08;我们约定空树不是任意一个树的子结构&#xff09; 假如给定A为{8,8,7,9,2,#,#,#,#,4,7}&#xff0c;B为{8,9,2}&#xff0c;2个树的结构如下&#xff…...

FFmpeg 4.3 音视频-多路H265监控录放C++开发六,使用SDLVSQT显示yuv文件

使用QT 显示YUV 文件 在最后一帧的时候会不停的显示最后一帧图片。 Vsqtshowyuv.h #pragma once#include <QtWidgets/QWidget> #include "ui_vsqtshowyuv.h" #include <sdl/SDL.h> #include <iostream> #include <fstream> #include <Q…...

Spring 设计模式之适配器模式

Spring 设计模式之适配器模式 适配器模式用到的场景java举例 适配器模式 适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许接口不兼容的类一起工作。 其核心思想是通过一个适配器类将不兼容的接口转换成客户端期望的另一个接口&…...

多传感器数字化分析系统

在工业飞速发展的今天&#xff0c;设备的安全稳定运行成为企业高效生产的关键因素。然而&#xff0c;传统的人工巡检方式面临着诸多挑战&#xff0c;如效率低下、漏检误检以及难以精准掌握设备运行状态等。旗晟凭借深厚的技术积累和创新精神&#xff0c;推出了多传感器数字化分…...

Java 基础教学:面向对象编程基础-封装、继承与多态

面向对象编程&#xff08;OOP&#xff09;是现代编程的重要范式&#xff0c;Java 语言提供了丰富的 OOP 特性&#xff0c;主要包括封装、继承和多态。本文将详细讲解这三个概念及其实现方式&#xff0c;并提供相应的代码示例。 1. 封装 1.1 概念 封装是将对象的状态&#xf…...

Ubuntu环境本地部署DbGate数据库管理工具并实现无公网IP远程访问

文章目录 前言1. 安装Docker2. 使用Docker拉取DbGate镜像3. 创建并启动DbGate容器4. 本地连接测试5. 公网远程访问本地DbGate容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定公网地址远程访问 前言 本文主要介绍如何在Linux Ubuntu系统中使用Docker部署DbGate数…...

【AI抠图整合包及教程】Meta SAM 2:视觉分割的革命性飞跃

在人工智能的浪潮中&#xff0c;每一次技术的革新都如同一场视觉盛宴&#xff0c;让我们见证着数字时代的变迁。Meta再次以Segment Anything Model 2&#xff08;SAM 2&#xff09;引领了图像和视频分割技术的新纪元。作为首个用于实时、可提示的图像和视频对象分割的统一模型&…...

使用语言模型进行文本摘要的五个级别(llm)

视频链接&#xff1a;5 Levels Of LLM Summarizing: Novice to Expert...

ubuntu交叉编译libffi库给arm平台使用

1.下载并解压&#xff1a; 2.生成makefile 编译&#xff1a; make 编译成功&#xff1a; 安装&#xff1a; make install 安装成功 查看安装后的libffi库...

【jvm】空间分配担保策略

目录 1. 说明2. 工作原理2.1 估算新生代存活对象大小2.2 判断老年代的剩余空间2.3 触发Full GC的条件 3. 相关参数与配置3.1 -XX:HandlePromotionFailure3.2 -XX:PretenureSizeThreshold3.3 -XX:MaxTenuringThreshold3.4 -XX:TargetSurvivorRatio 4.作用与意义 1. 说明 1.在Ja…...

iQOO手机怎样将屏幕投射到MacBook?可以同步音频吗?

众所周知&#xff0c;苹果品牌的设备自己有AirPlay的投屏功能&#xff0c;iPhone要投屏到MacBook只要连接同一网络&#xff0c;然后开启AirPlay就可以投屏。但其他品牌的手机没有AirPlay&#xff0c;怎么将手机屏幕投射到MacBook呢&#xff1f; 安卓系统的手机可以使用无线投屏…...

BUU usualCrypt1

查壳&#xff0c;32bit&#xff0c;丢进ida32中进行反编译&#xff0c;简单的不多说&#xff0c;直接进main分析 简单分析&#xff0c;打上注释&#xff0c;没啥好看的&#xff0c;就一个加密函数&#xff0c;加密完后和一个字符串进行比较&#xff0c;由此可以逆推出加密前的字…...

第十七章 标准库特殊设施

17.1 tuple类型 当希望将一些数据合成单一对象&#xff0c;但又不想麻烦地定义一个新数据结构来表示这些数据时&#xff0c;tuple非常有用。tuple是类似pair的模板。 tuple<size_t, size_t, size_t> threeD; //三个成员都设置为0//为每个成员提供初始值 tuple<strin…...

【格言分享】程序员的经典名言解读

上一期文章我们分享了一些程序员的经典名言,每一句都蕴含着深刻的道理。 接下来就给大家一个一个分析一下 这些格言确实捕捉到了编程和软件开发的精髓,每一条都蕴含着丰富的经验和智慧。下面我将逐一解释这些格言,并分享一些我的看法。 C程序员永远不会灭亡。他们只是cast…...

SpringBoot接收LocalDateTime参数

一、通过RequestBody接收 方式1&#xff1a;实体类上加上 JsonFormat&#xff0c;并通过 pattern 属性指定时间格式 public class Time {JsonFormat(pattern "yyyy-MM-dd HH:mm:ss")LocalDateTime localDateTime;JsonFormat(pattern "yyyy-MM-dd")Loca…...

Typora配置GitHub图床--结合PicGo

【当前问题】Typora文档分享时 无法看到本地路径图片 【怎么解决】把文档中的图片设置为 公开链接 【准备工具】 Typora 官网https://typoraio.cn/&#xff08;购买 / 自寻破解法&#xff09;GitHub账号 https://github.com/PicGo https://github.com/Molunerfinn/PicGo/relea…...

【书生.浦语实战营】——入门岛

【书生.浦语实战营】——入门岛_第一关_Linux基础 任务分布1. 本地vscode远程连接并进行端口映射端口映射What——何为端口映射How——怎么进行端口映射 2. Linux基础命令touch &#xff1a;创建文件mkdir &#xff1a;创建目录cd:进入 退出 目录pwd :确定当前所在目录cat:可以…...

WPF+MVVM案例实战(十四)- 封装一个自定义消息弹窗控件(下)

文章目录 1、案例效果2、弹窗控件使用1.引入用户控件2、按钮命令实现 3、总结4、源代码获取 1、案例效果 2、弹窗控件使用 1.引入用户控件 打开 Wpf_Examples 项目&#xff0c;在引用中添加用户控件库&#xff0c;在 MainWindow.xaml 界面引用控件库&#xff0c;代码如下&…...

嵌入式——STM32外设应用

STM32 微控制器以其高性能、低功耗和丰富的外设资源&#xff0c;在嵌入式系统设计中得到了广泛应用。以下将详细介绍 STM32 的主要外设及其典型应用&#xff0c;帮助开发者更好地理解和应用这些功能。 1. GPIO&#xff08;通用输入输出端口&#xff09; 功能&#xff1a;GPIO…...

HCIA(ACL)

第七节 ACL&#xff1a;访问控制列表 访问控制----在路由器的入或者出的接口上&#xff0c;匹配流量&#xff0c;之后产生动作---允许或拒绝 定义感兴趣流量-----帮助其他软件抓流量 匹配规则&#xff1a; 至上而下&#xff0c;逐一匹配&#xff0c;上调匹配按照上条执行…...

OpenClaw性能优化:GLM-4.7-Flash长任务链的Token节省技巧

OpenClaw性能优化&#xff1a;GLM-4.7-Flash长任务链的Token节省技巧 1. 问题背景&#xff1a;长任务链的Token消耗困境 上周我尝试用OpenClaw自动化处理一个典型的办公场景&#xff1a;从200页PDF中提取关键数据&#xff0c;整理成Excel表格后发送邮件。整个流程涉及PDF解析…...

F_Record:让Photoshop绘画过程录制变得简单高效的轻量级插件

F_Record&#xff1a;让Photoshop绘画过程录制变得简单高效的轻量级插件 【免费下载链接】F_Record 一款用来录制绘画过程的轻量级PS插件 项目地址: https://gitcode.com/gh_mirrors/fr/F_Record 在数字艺术创作领域&#xff0c;每一笔笔触都承载着创作者的灵感与思考。…...

Java中灵活转换日期时间字符串格式的教程

本教程详细介绍了如何使用Java Java8及更高版本.time API&#xff0c;准确地将各种不同格式的日期时间字符串转换为统一”DD.MM.YYYY“格式。本文强调了现代日期时间API的优势&#xff0c;分析了Datetimeformater模式符号的正确使用&#xff0c;并提供了完整的示例代码和最佳实…...

双模型混搭方案:OpenClaw同时接入百川2-13B与Qwen的实操演示

双模型混搭方案&#xff1a;OpenClaw同时接入百川2-13B与Qwen的实操演示 1. 为什么需要多模型混搭&#xff1f; 去年冬天&#xff0c;当我第一次尝试用OpenClaw自动化处理技术文档时&#xff0c;发现一个有趣的现象&#xff1a;同一个模型在不同任务上的表现差异巨大。Qwen在…...

从‘噬菌体’到清晰地图:我的LIO-SAM避坑实战记录(含Ubuntu版本选择建议)

从“噬菌体”到清晰地图&#xff1a;LIO-SAM实战避坑指南与Ubuntu版本选择建议 第一次在RViz里看到那个旋转成筒状的地图时&#xff0c;我盯着屏幕足足愣了三分钟——这和我预想中的高精度点云地图相差了十万八千里。更令人崩溃的是&#xff0c;当我把设备搬到室外测试时&#…...

【OpenClaw 全面解析:从零到精通】第 025 篇:OpenClaw v2026.3.22+v2026.3.23 安全与架构全面升级:从版本迭代看 AI Agent 工程化实践

系列说明&#xff1a;本系列全面介绍 OpenClaw 开源 AI 智能体框架&#xff0c;从历史背景到核心原理&#xff0c;从安装部署到应用生态。本文为系列第 025 篇&#xff0c;结合 2026 年 3 月 22-24 日最新发布的双版本合并更新&#xff0c;系统解析 OpenClaw 从功能驱动到安全驱…...

Path of Building完全指南:精准规划角色构筑3步法+高效配置策略

Path of Building完全指南&#xff1a;精准规划角色构筑3步法高效配置策略 【免费下载链接】PathOfBuilding Offline build planner for Path of Exile. 项目地址: https://gitcode.com/gh_mirrors/pat/PathOfBuilding Path of Building是一款强大的离线工具&#xff0c…...

Python实战:5分钟搞定分数傅里叶变换(FRFT)的数值计算与可视化

Python实战&#xff1a;5分钟搞定分数傅里叶变换&#xff08;FRFT&#xff09;的数值计算与可视化 在信号处理领域&#xff0c;傅里叶变换早已成为工程师们的标准工具&#xff0c;但你是否想过&#xff0c;在时域和频域之间还存在无数个"中间态"&#xff1f;这就是分…...

终极指南:RealChar语音识别技术深度对比——Whisper、Google Speech与本地部署方案

终极指南&#xff1a;RealChar语音识别技术深度对比——Whisper、Google Speech与本地部署方案 【免费下载链接】RealChar &#x1f399;️&#x1f916;Create, Customize and Talk to your AI Character/Companion in Realtime (All in One Codebase!). Have a natural seaml…...

从零搭建一个HarmonyOS版GitCode客户端:我的React Native项目目录结构与配置心得

从零搭建HarmonyOS版GitCode客户端的工程化实践 作为一名长期耕耘在跨平台开发领域的技术实践者&#xff0c;我最近完成了基于React Native的HarmonyOS版GitCode客户端开发。这个项目让我深刻体会到&#xff0c;良好的项目结构设计比功能实现更重要——它直接影响团队协作效率和…...