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.提交结果

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/34026.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

天天AI-241302:今日热点-B站第二届超级科学晚聚焦AIGC,年度播放量突破300亿次

2AGI.NET 天天 AI 天天AI&#xff1a;AIGC技术引领科学与媒体新浪潮天天AI&#xff1a;AIGC技术引领科学与媒体新浪潮https://www.2agi.net/blog/daily-ai-aigc-technology-leads-science-and-media-new-wave/ 1. B站第二届超级科学晚聚焦AIGC&#xff0c;年度播放量突破300亿…

MySQL数据集成到广东省追溯平台的销售信息同步方案

销售信息同步--外购上报流程2&#xff1a;MySQL数据集成到广东省特殊食品电子追溯平台 在现代数据驱动的业务环境中&#xff0c;确保销售信息的准确性和及时性至关重要。本文将分享一个具体的技术案例&#xff0c;展示如何通过轻易云数据集成平台&#xff0c;将MySQL中的销售信…

vue-qr在线生成二维码组件(vue2版本)

在对于二维码生成中有许多组件&#xff0c;下面介绍关于自定义比较高的vue-qr组件&#xff0c;能自定义设置背景颜色、背景图片、背景Gif图、实点和空白区的颜色、中心Logo的图片和边距。 依赖下载 注意&#xff1a; 直接npm下载最新版 有些项目可能运行会抱错 这时候你可以降…

C#/.NET/.NET Core技术前沿周刊 | 第 15 期(2024年11.25-11.30)

前言 C#/.NET/.NET Core技术前沿周刊&#xff0c;你的每周技术指南针&#xff01;记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿&#xff0c;助力技术成长与视野拓宽。 欢迎投稿、推荐…

Ngrok快速将你的本地Streamlit应用创建一个公共的 URL,供外网访问

目录 1 Ngrok介绍2 Ngrok 的工作原理3 Ngrok安装4 启动Streamlit应用5 Ngrok搭建外网访问 1 Ngrok介绍 Ngrok 是一个开源工具和商业服务&#xff0c;可以为你的本地应用创建一个安全的公共 URL&#xff0c;使其能够通过互联网访问&#xff0c;而无需复杂的网络配置&#xff08…

青龙面板的定时规则

6个数字的定时规则&#xff0c; 第1个是秒&#xff0c;第2个是分&#xff0c;第3个是时&#xff0c;第4个是每月的哪日&#xff0c;第5个是哪月&#xff0c;第6个是每周的周几。 数字之间空格隔开。 不限制的用*号替代&#xff0c;定期的时间用“?”替代&#xff0c;间隔运…

XSS(DOM)-HIGH错误总结

HIGH就不从简单的开始。 我们直接闭合HTML标签绕过 ></option></select><img srcx:alert(alt) οnerrοreval(src) altxss> 没有变化 这里应该是后端的问题&#xff0c;试试锚点注入 English#<script>alert(xss)</script> 这里不知道什么…

深度学习图像增强介绍

目录 一、引言二、常用数据增广方法三、图像变换类3.1 AutoAugment3.2 RandAugment 四、图像裁剪类4.1 Cutout4.2 RandomErasing4.3 HideAndSeek 五、图像混叠5.1 Mixup5.2 Cutmix 六、结论 一、引言 在图像分类任务中&#xff0c;图像数据的增广是一种常用的正则化方法&#…

MySQL导入.sql文件后数据库乱码问题

问题分析&#xff1a; 当导入.sql文件后&#xff0c;发现数据库中的备注出现乱码&#xff0c;通常是由于一下原因导致&#xff1a; 字符集不匹配&#xff1a;.sql文件、MySQL服务器、客户端连接使用的字符集不一致。备注内容编码问题&#xff1a;备注内容本身的编码格式与数据…

云数据库 RDS

云数据库 RDS&#xff08;Relational Database Service&#xff0c;关系型数据库服务&#xff09;是由阿里云提供的一种托管的关系型数据库服务&#xff0c;旨在简化数据库的部署、管理和维护工作&#xff0c;帮助用户快速构建、部署和管理关系型数据库。RDS 提供了包括 MySQL、…

图社区发现算法-Louvain算法

Louvain社区发现算法出自2008年的论文《Fast unfolding of communities in large networks》&#xff0c;其名字是根据作者所在的城市来命名的。它基于模块度优化来实现社区划分。 准备知识 模块度(modularity)是用来衡量社区内部的链接密度相比社区之间的链接密度的介于-1和…

Elasticsearch之索引的增删改查(6.x版本)-yellowcong

1. 节点信息查看 #查看集群健康情况 curl -X GET localhost:9200/_cat/health?v&pretty#查看节点信息 curl -X GET localhost:9200/_cat/nodes?v&pretty 2. 索引管理 在es中&#xff0c;索引就相当于是mysql中的库了。 #查看索引列表 curl -X GET localhost:9200/…

技术栈4:Docker入门 Linux入门指令

目录 1.Linux系统目录结构 2.处理目录的常用命令 3.Docker概述 4.Docker历史 5.Docker基本组成 6.Docker底层原理 7.Docker修改镜像源 8.Docker基本命令 在学习docker之前我们先要熟悉Linux系统&#xff0c;推荐阅读&#xff1a;Linux笔记&#xff08;狂神说&#xff0…

UFS文档导航

目录 1、UFS系统模型 2、UFS子系统实现架构 3、Host Controller 4、M-PHY 5、UFS Device 1、UFS系统模型 2、UFS子系统实现架构 3、Host Controller 模块 文档名称 文档描述 Host Controller JESD223D 协议文档&#xff0c;UFS Host Controller Interface DWC_ufshc…

北斗系统:构建天地一体化的高精度定位服务

随着北斗卫星导航系统的全面建成&#xff0c;中国在全球卫星导航领域迈出了坚实的一步。北斗系统不仅提供了全天候、全天时的全球覆盖服务能力&#xff0c;更通过天地一体化的高精度增强服务系统技术&#xff0c;将民用定位精度提升到了新的高度。 北斗系统的高精度服务 北斗…

论文阅读:Omnidirectional Image Super-resolution via Bi-projection Fusion

对于全景图像&#xff08;ODIs&#xff09;的超分辨率的技术有&#xff1a;等矩投影&#xff08;ERP&#xff09;但是这个没有利用 ODIs 的独特任何特性。ERP提供了完整的视场但引入了显著的失真&#xff0c;而立方体映射投影&#xff08;CMP&#xff09;可以减少失真但视场有限…

汽车总线协议分析-FlexRay总线

随着汽车智能化发展&#xff0c;汽车增加安全性和舒适体验的功能增多&#xff0c;用于实现这些功能的传感器、ECU的数量也在持续上升&#xff0c;严重阻碍了线控技术的发展。常用的CAN、LIN等总线由于缺少同步性、确定性和容错性不能满足汽车线控系统(X-by-Wire)的要求。因此&a…

《算法导论》英文版前言To the teacher第4段研习录:有答案不让用

【英文版】 Departing from our practice in previous editions of this book, we have made publicly available solutions to some, but by no means all, of the problems and exercises. Our Web site, http://mitpress.mit.edu/algorithms/, links to these solutions. Y…

AI Agent工作流程:关于是使用 LangGraph 还是 LangChain 进行构建的完整指南

深入了解同一创建者 LangChain 和 LangGraph 的两个库&#xff1a;它们的关键构建块、它们如何处理其功能的核心部分&#xff0c;以及为您的用例在它们之间做出决定 语言模型为用户如何与 AI 系统交互以及这些系统如何通过自然语言相互通信开启了可能性。 在本文中&#xff0c…

qt QPrinter详解

1、概述 QPrinter类是Qt框架中用于打印输出的绘图设备。它表示打印出来的一系列页面&#xff0c;并提供了一组附加功能来管理特定于设备的特性&#xff0c;比如方向和分辨率。QPrinter可以生成PDF文档&#xff0c;也可以将内容发送到打印机进行实际打印。它继承自QPagedPaintD…