(树) 剑指 Offer 26. 树的子结构 ——【Leetcode每日一题】
❓剑指 Offer 26. 树的子结构
难度:中等
输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)
B 是 A 的子结构, 即 A 中有出现和B相同的结构和节点值。
例如:
给定的树 A:
3/ \4 5/ \1 2
给定的树 B:
4 /1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1:
输入:A = [1,2,3], B = [3,1]
输出:false
示例 2:
输入:A = [3,4,5,1,2], B = [4,1]
输出:true
限制:
0 <= 节点个数 <= 10000
💡思路:递归
二叉树 B 为 A 的子结构的情况一共有三种,满足其中一种即可:
- 子结构
B的起点为A的根节点,即从A的根节点开始和B比较, 调用函数isSubStree:- 不相等,则返回
false; - 相等,则再比较 左子树和右子树都是否相等,都相等,才返回
true
- 不相等,则返回
- 子结构
B在A的左子树中,即B的起点隐藏在A的左子树中,此时调用函数isSubStructure; - 子结构
B在A的右子树中,即B的起点隐藏在A的右子树中,此时调用函数isSubStructure。
🍁代码:(C++、Java)
C++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
private:bool isSubStree (TreeNode* root1, TreeNode* root2){if(root2 == nullptr) return true;if(root1 == nullptr) return false;if(root1->val != root2->val) return false;return isSubStree(root1->left, root2->left) && isSubStree(root1->right, root2->right);}
public:bool isSubStructure(TreeNode* A, TreeNode* B) {if(A == nullptr || B == nullptr) return false;return isSubStree(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);}
};
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {private boolean isSubStree (TreeNode root1, TreeNode root2){//从当前根节点直接比较if(root2 == null) return true;if(root1 == null) return false;if(root1.val != root2.val) return false;return isSubStree(root1.left, root2.left) && isSubStree(root1.right, root2.right);}public boolean isSubStructure(TreeNode A, TreeNode B) {if(A == null || B == null) return false;return isSubStree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( n m ) O(nm) O(nm),其中
n和m分别表示两棵树的节点数,我们要对每个A树节点进行访问,最坏情况下每次都要比较B树节点的次数。 - 空间复杂度: O ( n + m ) O(n + m) O(n+m),两个递归栈深度相乘(当树退化成链表时,递归栈最大)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(树) 剑指 Offer 26. 树的子结构 ——【Leetcode每日一题】
❓剑指 Offer 26. 树的子结构 难度:中等 输入两棵二叉树 A 和 B,判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构) B 是 A 的子结构, 即 A 中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3/ \4 5/ \1 2给定的树 B&…...
Linuxcnc-ethercat从入门到放弃(1)、环境搭建
项目开源网站 LinuxCNChttps://www.linuxcnc.org/当前release版本2.8.4 Downloads (linuxcnc.org)https://www.linuxcnc.org/downloads/可以直接下载安装好linuxcnc的实时debian系统,直接刻盘安装就可以了 安装IgH主站,网上有很多教程可供参考 git clo…...
14.Netty源码之模拟简单的HTTP服务器
highlight: arduino-light 简单的 HTTP 服务器 HTTP 服务器是我们平时最常用的工具之一。同传统 Web 容器 Tomcat、Jetty 一样,Netty 也可以方便地开发一个 HTTP 服务器。我从一个简单的 HTTP 服务器开始,通过程序示例为你展现 Netty 程序如何配置启动&a…...
万年历【小游戏】(Java课设)
系统类型 Java实现的小游戏 使用范围 适合作为Java课设!!! 部署环境 jdk1.8Idea或eclipse 运行效果 更多Java课设系统源码地址:更多Java课设系统源码地址 更多Java小游戏运行效果展示:更多Java小游戏运行效果展…...
ad+硬件每日学习十个知识点(9)23.7.20
文章目录 1.正点原子fpga开拓者无gui检查项目2.排针连接器A2541WR-XP-2P3.肖特基二极管反接在LDO的输出端,是什么用?4.在AD中如何实现批量元器件的移动?5.在PCB中,如何让元器件以任意角度旋转?6.接口设计都要做静电防护…...
ipmitool 配置BMC的ip
要使用ipmitool配置BMC的IP地址,可以按照以下步骤进行操作: 确保已安装ipmitool工具。如果尚未安装,可以使用以下命令进行安装: |复制代码 sudo yum install ipmitool连接到BMC:使用IPMI-over-LAN(通过网…...
C++设计模式::小结(creation)
creation:隐藏创建逻辑. 1) 抽象工厂模式(Abstract Factory Pattern):多层次"任选"创建对象; 实现: 1) cShape:抽象对象; cShape*:具体对象; 2) cColor:抽象对象; cColor*:具体对象; 3) cFacto…...
运维工程师第一阶段windows的学习
文章目录 计算机硬件组成计算机历史计算机硬件组成最重要的三个硬件冯诺依曼体系:组装一台电脑:虚拟机和装系统虚拟机VMware安装系统搭建局域网本地安全策略用户本地安全策略共享文件删除操作系统操作系统分类系统优化常用命令系统的启动和密码破解winodws启动过程windows系统…...
Docker复习
目录 1. Docker的理解1.1 Docker三要素 2 安装Docker2.1 安装命令2.2 配置阿里云加速器 3 Docker命令3.1 启动类命令3.2 镜像类命令 4 实战4.1 启动容器,自动创建实例4.2 查看Docker内启动的容器4.3 退出容器4.4 其他4.5 导入导出文件4.6 commit 5 Dockerfile5.1 理…...
华为OD机考--食堂供餐--带答案
题目描述: 某公司员工食堂以盒饭方式供餐。为将员工取餐排队时间降低为0,食堂的供餐速度必须要足够快。现在需要根据以往员工取餐的统计信息,计算出一个刚好能达成排队时间为0的最低供餐速度。即,食堂在每个单位时间内必须至少做出…...
C# 关于使用newlife包将webapi接口寄宿于一个控制台程序、winform程序、wpf程序运行
C# 关于使用newlife包将webapi接口寄宿于一个控制台程序、winform程序、wpf程序运行 安装newlife包 Program的Main()函数源码 using ConsoleApp3; using NewLife.Log;var server new NewLife.Http.HttpServer {Port 8080,Log XTrace.Log,SessionLog XTrace.Log }; serv…...
初识TDMQ
目录 一:需求背景二:相关文档三:验证TDMQ广播消息 一:需求背景 目前公司需要将决策引擎处理的结果, 一部分数据交给下游分析/入黑/通知等功能。因此就需要决策引擎生产结果让多方下游去消费。 而我需要实现下游的一部…...
UEditor 百度富文本编辑器使用 遇到问题
小小吐槽 碰到前后不分离项目,富文本使用的UEdtior UEditor 点击上传图片转base64 在ueditor.all.js文件中找到这个 callback()函数 这里使用根据图片的url转成base64 UEditore 粘贴图片转base64 UEditor回显图片(base64) 把ueditor.all…...
jaeger+elasticsearch(cassandra ) 单机部署以及(400)报错
Jaeger 快速体验 官网下载地址 https://www.jaegertracing.io/download/ GitHub 下载地址 https://github.com/jaegertracing/jaeger/releases 下载二进制文件压缩包后,运行解压后的 all-in-one 文件即可。 jaeger-all-in-one 采用内存存储数据,专为…...
VSCode配置之C++ SQLite3极简配置方案
背景 最近在学习《深入应用C11: 代码优化与工程级应用》,其中第13章说到SQLite库,查询网上诸多教程,发现比较容易出现bug且配置较为麻烦,故记录此次简化版方案,以供参考。 软件环境 SQLite 3.42.0 版本(仅…...
P5725 【深基4.习8】求三角形
题目描述 模仿例题,打印出不同方向的正方形,然后打印三角形矩阵。中间有个空行。 输入格式 输入矩阵的规模,不超过 9 9 9。 输出格式 输出矩形和正方形 1.题目分析 循环判断就可以解决,总的来说,是个比较简单的…...
分布式消息中间件介绍
什么是分布式消息中间件? 对于分布式消息中间件,首先要了解两个基础的概念,即什么是分布式系统,什么又是中间件。 分布式系统 “A distributed system is one in which components located at networked computers communicate an…...
【Linux进程篇】冯诺依曼体系
【Linux进程篇】冯诺依曼体系 目录 【Linux进程篇】冯诺依曼体系冯诺依曼体系结构(1/3内容 )操作系统(Operator System)概念设计OS的目的定位如何理解“管理”总结系统调用和库函数的概念 作者:爱写代码的刚子 时间:2023.7.28 前言…...
陕西师范大学大学:融合传统与创新的学府之旅
前言 > 📕作者简介:热爱跑步的恒川,致力于C/C、Java、Python等多编程语言,热爱跑步,喜爱音乐的一位博主。 > 📗本文收录于恒川的日常汇报系列,大家有兴趣的可以看一看 > Ὅ…...
HTML <progress> 标签
实例 正在进行的下载: <progress value"22" max"100"></progress> 浏览器支持 元素ChromeIEFirefoxSafariOpera<progress>8.010.016.06.011.0 定义和用法 <progress> 标签标示任务的进度(进程…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
省略号和可变参数模板
本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...
