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

L17.【LeetCode笔记】另一棵树的子树

目录

1.题目

代码模板

2.分析

3.代码

4.提交结果


1.题目

https://leetcode.cn/problems/subtree-of-another-tree/description/

给你两棵二叉树 rootsubRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1:

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

示例 2:

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:false

提示:

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

代码模板

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{
}

2.分析

题目的意思是在整棵二叉树中寻找特定的子树(局部相等)

检查是否包含subroot,即寻找相同的子树,因此可以直接调用L15.【LeetCode笔记】相同的树文章的代码,如下

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if (p==NULL && q==NULL)return true;//若能执行到此,排除了两个都为NULL的情况,剩下的情况:1.其中一个为NULL;2.两个都不为NULLif ((p==NULL)+(q==NULL)==1)return false;//只剩下最后一种情况:p和q都不为NULLif (p->val!=q->val)return false;//执行到此处,说明p->val和q->val相等return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

现在的问题转化为如何设计isSubtree函数使其能合理调用isSameTree函数


由于subRoot肯定不为空树,因此上来先判断root==NULL

    if(root==NULL)return false;

除去了这种情况,剩下root!=NULL,把每个节点视作根去寻找子树,判断子树是否相等

可以判断isSameTree(root,sunRoot)的返回值,再进一步操作

    if (isSameTree(root,subRoot))return true;

如果上方函数的返回值为false,情况有两种:1.完全找不到符合subRoot的子树 2.不是要找的子树,需要进一步查找(root->left和root->right)

注意:只要左右子树有一个符合要求就可以,因此用或(||)连接

return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);

递归展开图(只画isSameTree),以下面这个二叉树为例说明

注:CSDN会压缩图片画质,无损bmp图片链接(大小 9.28M)见百度网盘 请输入提取码

3.代码

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if (p==NULL && q==NULL)return true;//若能执行到此,排除了两个都为NULL的情况,剩下的情况:1.其中一个为NULL;2.两个都不为NULLif ((p==NULL)+(q==NULL)==1)return false;//只剩下最后一种情况:p和q都不为NULLif (p->val!=q->val)return false;//执行到此处,说明p->val和q->val相等return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) 
{if (root==NULL)return false;if (isSameTree(root,subRoot))return true;return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);}

4.提交结果

相关文章:

L17.【LeetCode笔记】另一棵树的子树

目录 1.题目 代码模板 2.分析 3.代码 4.提交结果 1.题目 https://leetcode.cn/problems/subtree-of-another-tree/description/ 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在&#xff0c;返回 true &#xff…...

BGP通过route-policy路由策略调用ip-prefix网络前缀实现负载均衡与可靠性之AS-path属性

一、实验场景 1、loopback0与loopback1模拟企业实际环境中的某个网段。 2、本例目标总公司AR3的1.1.1.1/32网段到分公司AR4的3.3.3.3/32的流量从上方的AS500自治系统走。 3、本例目标总公司AR3的4.4.4.4/32网段到分公司AR4的2.2.2.2/32的流量从下面的AS300、AS400自治系统走。…...

每日速记10道java面试题14-MySQL篇

其他资料 每日速记10道java面试题01-CSDN博客 每日速记10道java面试题02-CSDN博客 每日速记10道java面试题03-CSDN博客 每日速记10道java面试题04-CSDN博客 每日速记10道java面试题05-CSDN博客 每日速记10道java面试题06-CSDN博客 每日速记10道java面试题07-CSDN博客 每…...

内存图及其画法

所有的文件都存在硬盘上&#xff0c;首次使用的时候才会进入内存 进程&#xff1a;有自己的Main方法&#xff0c;并且依赖自己Main运行起来的程序。独占一块内存区域&#xff0c;互不干扰。内存中有一个一个的进程。 操作系统只认识c语言。操作系统调度驱动管理硬件&#xff0…...

Ansys Maxwell:Qi 无线充电组件

Qi 无线充电采用感应充电技术&#xff0c;无需物理连接器或电缆&#xff0c;即可将电力从充电站传输到兼容设备。由 WPC 管理的 Qi 标准确保了不同无线充电产品之间的互操作性。以下是 Qi v1.3 标准的核心功能&#xff1a; Qi v1.3 标准的主要特点 身份验证&#xff1a;确保充…...

【Shell 脚本实现 HTTP 请求的接收、解析、处理逻辑】

以下是一个实现客户端对 Shell HTTP 服务发起 POST 请求并传入 JSON 参数的完整示例。Shell 服务会解析收到的 JSON 数据&#xff0c;根据内容执行操作。 服务端脚本&#xff1a;http_server.sh 以下脚本使用 netcat (nc) 来监听 HTTP 请求&#xff0c;并通过 jq 工具解析 JSO…...

【北京迅为】iTOP-4412全能版使用手册-第六十七章 USB鼠标驱动详解

iTOP-4412全能版采用四核Cortex-A9&#xff0c;主频为1.4GHz-1.6GHz&#xff0c;配备S5M8767 电源管理&#xff0c;集成USB HUB,选用高品质板对板连接器稳定可靠&#xff0c;大厂生产&#xff0c;做工精良。接口一应俱全&#xff0c;开发更简单,搭载全网通4G、支持WIFI、蓝牙、…...

【青牛科技】拥有两个独立的、高增益、内部相位补偿的双运算放大器,可适用于单电源或双电源工作——D4558

概述&#xff1a; D4558内部包括有两个独立的、高增益、内部相位补偿的双运算放大器&#xff0c;可适用于单电源或双电源工作。该电路具有电压增益高、噪声低等特点。主要应用于音频信号放大&#xff0c;有源滤波器等场合。 D4558采用DIP8、SOP8的封装形式 主要特点&#xff…...

Kafka 数据写入问题

目录标题 分析思路1. **生产者配置问题**&#xff1a;Kafka生产者的配置参数生产者和消费者的处理确定并优化 2. **网络问题**&#xff1a;3. **Kafka 集群配置问题**&#xff1a;unclean.leader.election.enable 4. **Zookeeper 配置问题**&#xff1a;5. **JVM 参数调优**&am…...

实战ansible-playbook(九)-profile配置- 确保 CUDA 和 MPI 环境变量正确设置并立即生效

Playbook 分析 --- - name: 确保 CUDA 和 MPI 环境变量正确设置并立即生效hosts: pod2 # 指定目标主机组或具体主机名become: yes # 使用特权提升(sudo),以root权限执行某些需要权限的任务remote_user: canopy # 远程连接使用的用户名vars: # 定义全局变量,用于Playbo…...

气膜馆:科技与环保融合的未来建筑新选择—轻空间

在全球城市化进程不断加快的背景下&#xff0c;传统建筑方式面临着越来越多的挑战。如何在有限的土地和资源条件下&#xff0c;快速、高效、环保地搭建符合多功能需求的建筑&#xff0c;成为现代建筑行业亟待解决的重要课题。而随着科技的进步与建筑材料的创新&#xff0c;一种…...

git回退到某个版本git checkout和git reset命令的区别

文章目录 1. git checkout <commit>2. git reset --hard <commit>两者的区别总结推荐使用场景* 在使用 Git 回退到某个版本时&#xff0c; git checkout <commit> 和 git reset --hard <commit> 是两种常见的方式&#xff0c;但它们的用途和影响有很…...

Preprocess

Preprocess数据预处理 文本 使用Tokenizer将文本转换为标记序列&#xff0c;创建标记的数值表示&#xff0c;并将它们组装成张量。 预处理文本数据的主要工具是标记器。标记器根据一组规则将文本拆分为标记。标记被转换为数字&#xff0c;然后转换为张量&#xff0c;这些张量…...

stm32 spi接口传输asm330l速率优化(及cpu和dma方式对比)

最近一段时间做了一个mems的项目&#xff0c;项目的方案是stm32g071做主控&#xff0c;读写3颗asm330l的硬件形态。最初是想放置4颗imu芯片&#xff0c;因为pcb空间布局的问题&#xff0c;改放了3颗。但对于软件方案来说无所谓&#xff0c;关键是如何优化spi的传输速率&#xf…...

数字时代的文化宝库:存储技术与精神生活

文章目录 1. 文学经典的数字传承2. 音乐的无限可能3. 影视艺术的数字化存储4. 结语 数字时代的文化宝库&#xff1a;存储技术与精神生活 在数字化的浪潮中&#xff0c;存储技术如同一座桥梁&#xff0c;连接着过去与未来&#xff0c;承载着人类文明的瑰宝。随着存储容量的不断增…...

flex: 1 display:flex 导致的宽度失效问题

flex: 1 & display:flex 导致的宽度失效问题 问题复现 有这样的一个业务场景&#xff0c;详情项每行三项分别占33%宽度&#xff0c;每项有label字数不固定所以宽度不固定&#xff0c;还有content 占满标签剩余宽度&#xff0c;文字过多显示省略号&#xff0c; 鼠标划入展示…...

Hive 窗口函数与分析函数深度解析:开启大数据分析的新维度

Hive 窗口函数与分析函数深度解析&#xff1a;开启大数据分析的新维度 在当今大数据蓬勃发展的时代&#xff0c;Hive 作为一款强大的数据仓库工具&#xff0c;其窗口函数和分析函数犹如一把把精巧的手术刀&#xff0c;助力数据分析师们精准地剖析海量数据&#xff0c;挖掘出深…...

前端工程 Node 版本如何选择

1. Node 与 Npm 版本对应 这是一个必知必会的问题&#xff0c;尤其是对于维护那些老掉牙、一坨坨、非常大的有着长期历史的老破大工程。 1.1. package-lock.json 版本 首先你要会看项目的 package-lock.json 文件中的 lockfileVersion 版本号&#xff0c;这对于 NPM 安装来说…...

推荐在线Sql运行

SQL Fiddle 1、网址&#xff1a;SQL Fiddle - Online SQL Compiler for learning & practiceDiscover our free online SQL editor enhanced with AI to chat, explain, and generate code. Support SQL Server, MySQL, MariaDB, PostgreSQL, and SQLite.http://www.sqlfi…...

【数据结构】【线性表】特殊的线性表-字符串

目录 字符串的基本概念 字符串的三要素 字符串的基本概念 串的编码 串的实现及基本运算 顺序串的实现 串的静态数组实现 串的动态数组的实现 顺序存储的四种方案 链式串的实现 基本运算 方案三 方案一 字符串的基本概念 数据结构千千万&#xff0c…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

联邦学习带宽资源分配

带宽资源分配是指在网络中如何合理分配有限的带宽资源&#xff0c;以满足各个通信任务和用户的需求&#xff0c;尤其是在多用户共享带宽的情况下&#xff0c;如何确保各个设备或用户的通信需求得到高效且公平的满足。带宽是网络中的一个重要资源&#xff0c;通常指的是单位时间…...