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…...
【数据结构】【线性表】特殊的线性表-字符串
目录 字符串的基本概念 字符串的三要素 字符串的基本概念 串的编码 串的实现及基本运算 顺序串的实现 串的静态数组实现 串的动态数组的实现 顺序存储的四种方案 链式串的实现 基本运算 方案三 方案一 字符串的基本概念 数据结构千千万,…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...


