L17.【LeetCode笔记】另一棵树的子树
目录
1.题目
代码模板
2.分析
3.代码
4.提交结果
1.题目
https://leetcode.cn/problems/subtree-of-another-tree/description/
给你两棵二叉树
root和subRoot。检验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 具有相同结构和节点值的子树。如果存在,返回 true ÿ…...
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博客 每…...
内存图及其画法
所有的文件都存在硬盘上,首次使用的时候才会进入内存 进程:有自己的Main方法,并且依赖自己Main运行起来的程序。独占一块内存区域,互不干扰。内存中有一个一个的进程。 操作系统只认识c语言。操作系统调度驱动管理硬件࿰…...
Ansys Maxwell:Qi 无线充电组件
Qi 无线充电采用感应充电技术,无需物理连接器或电缆,即可将电力从充电站传输到兼容设备。由 WPC 管理的 Qi 标准确保了不同无线充电产品之间的互操作性。以下是 Qi v1.3 标准的核心功能: Qi v1.3 标准的主要特点 身份验证:确保充…...
【Shell 脚本实现 HTTP 请求的接收、解析、处理逻辑】
以下是一个实现客户端对 Shell HTTP 服务发起 POST 请求并传入 JSON 参数的完整示例。Shell 服务会解析收到的 JSON 数据,根据内容执行操作。 服务端脚本:http_server.sh 以下脚本使用 netcat (nc) 来监听 HTTP 请求,并通过 jq 工具解析 JSO…...
【北京迅为】iTOP-4412全能版使用手册-第六十七章 USB鼠标驱动详解
iTOP-4412全能版采用四核Cortex-A9,主频为1.4GHz-1.6GHz,配备S5M8767 电源管理,集成USB HUB,选用高品质板对板连接器稳定可靠,大厂生产,做工精良。接口一应俱全,开发更简单,搭载全网通4G、支持WIFI、蓝牙、…...
【青牛科技】拥有两个独立的、高增益、内部相位补偿的双运算放大器,可适用于单电源或双电源工作——D4558
概述: D4558内部包括有两个独立的、高增益、内部相位补偿的双运算放大器,可适用于单电源或双电源工作。该电路具有电压增益高、噪声低等特点。主要应用于音频信号放大,有源滤波器等场合。 D4558采用DIP8、SOP8的封装形式 主要特点ÿ…...
Kafka 数据写入问题
目录标题 分析思路1. **生产者配置问题**:Kafka生产者的配置参数生产者和消费者的处理确定并优化 2. **网络问题**:3. **Kafka 集群配置问题**:unclean.leader.election.enable 4. **Zookeeper 配置问题**:5. **JVM 参数调优**&am…...
实战ansible-playbook(九)-profile配置- 确保 CUDA 和 MPI 环境变量正确设置并立即生效
Playbook 分析 --- - name: 确保 CUDA 和 MPI 环境变量正确设置并立即生效hosts: pod2 # 指定目标主机组或具体主机名become: yes # 使用特权提升(sudo),以root权限执行某些需要权限的任务remote_user: canopy # 远程连接使用的用户名vars: # 定义全局变量,用于Playbo…...
气膜馆:科技与环保融合的未来建筑新选择—轻空间
在全球城市化进程不断加快的背景下,传统建筑方式面临着越来越多的挑战。如何在有限的土地和资源条件下,快速、高效、环保地搭建符合多功能需求的建筑,成为现代建筑行业亟待解决的重要课题。而随着科技的进步与建筑材料的创新,一种…...
git回退到某个版本git checkout和git reset命令的区别
文章目录 1. git checkout <commit>2. git reset --hard <commit>两者的区别总结推荐使用场景* 在使用 Git 回退到某个版本时, git checkout <commit> 和 git reset --hard <commit> 是两种常见的方式,但它们的用途和影响有很…...
Preprocess
Preprocess数据预处理 文本 使用Tokenizer将文本转换为标记序列,创建标记的数值表示,并将它们组装成张量。 预处理文本数据的主要工具是标记器。标记器根据一组规则将文本拆分为标记。标记被转换为数字,然后转换为张量,这些张量…...
stm32 spi接口传输asm330l速率优化(及cpu和dma方式对比)
最近一段时间做了一个mems的项目,项目的方案是stm32g071做主控,读写3颗asm330l的硬件形态。最初是想放置4颗imu芯片,因为pcb空间布局的问题,改放了3颗。但对于软件方案来说无所谓,关键是如何优化spi的传输速率…...
数字时代的文化宝库:存储技术与精神生活
文章目录 1. 文学经典的数字传承2. 音乐的无限可能3. 影视艺术的数字化存储4. 结语 数字时代的文化宝库:存储技术与精神生活 在数字化的浪潮中,存储技术如同一座桥梁,连接着过去与未来,承载着人类文明的瑰宝。随着存储容量的不断增…...
flex: 1 display:flex 导致的宽度失效问题
flex: 1 & display:flex 导致的宽度失效问题 问题复现 有这样的一个业务场景,详情项每行三项分别占33%宽度,每项有label字数不固定所以宽度不固定,还有content 占满标签剩余宽度,文字过多显示省略号, 鼠标划入展示…...
Hive 窗口函数与分析函数深度解析:开启大数据分析的新维度
Hive 窗口函数与分析函数深度解析:开启大数据分析的新维度 在当今大数据蓬勃发展的时代,Hive 作为一款强大的数据仓库工具,其窗口函数和分析函数犹如一把把精巧的手术刀,助力数据分析师们精准地剖析海量数据,挖掘出深…...
前端工程 Node 版本如何选择
1. Node 与 Npm 版本对应 这是一个必知必会的问题,尤其是对于维护那些老掉牙、一坨坨、非常大的有着长期历史的老破大工程。 1.1. package-lock.json 版本 首先你要会看项目的 package-lock.json 文件中的 lockfileVersion 版本号,这对于 NPM 安装来说…...
推荐在线Sql运行
SQL Fiddle 1、网址: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…...
【数据结构】【线性表】特殊的线性表-字符串
目录 字符串的基本概念 字符串的三要素 字符串的基本概念 串的编码 串的实现及基本运算 顺序串的实现 串的静态数组实现 串的动态数组的实现 顺序存储的四种方案 链式串的实现 基本运算 方案三 方案一 字符串的基本概念 数据结构千千万,…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》
🧠 LangChain 中 TextSplitter 的使用详解:从基础到进阶(附代码) 一、前言 在处理大规模文本数据时,特别是在构建知识库或进行大模型训练与推理时,文本切分(Text Splitting) 是一个…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...


