【leetcode】相同的树、另一棵树的子树、翻转二叉树(利用深度优先遍历)
Hi~!这里是奋斗的明志,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~~
🌱🌱个人主页:奋斗的明志
🌱🌱所属专栏:数据结构、LeetCode专栏
📚本系列文章为个人学习笔记,在这里撰写成文一为巩固知识,二为展示我的学习过程及理解。文笔、排版拙劣,望见谅。
链表面试题
- 前言
- 一、相同的树
- 1. 题目
- 2. 解析
- 3. 完整代码
- 二、另一棵树的子树
- 1. 题目
- 2. 解析(深度优先搜索暴力匹配)
- 3. 完整代码
- 4.深度优先搜索序列上做串匹配
- 三、翻转二叉树
- 1.题目
- 2.解析(利用深度优先搜索)
- 3.完整代码
- 四、总结
前言
一定要结合图像来写题,递归有点绕
一、相同的树
100.相同的树
1. 题目
2. 解析
- 一个为空,一个不为空,说明不是两棵相同的树
- 如果两个都为空,说明是相同的树
- 两个都不为空,但是值不一样,说明不是两棵相同的树
isSameTree 方法解释:
-
参数:方法接收两个 TreeNode 类型的参数 p 和 q,分别代表两棵二叉树的根节点。
返回值:返回一个布尔值,表示两棵树是否相同。 -
逻辑:
首先,通过判断根节点的情况来确定树的结构是否相同:
如果 p 为 null 而 q 不为 null,或者 p 不为 null 而 q 为 null,则树的结构不同,返回 false。
如果两个根节点都为 null,说明两棵树为空树,返回 true。
如果根节点的值 p.val 不等于 q.val,则根节点的值不同,返回 false。
如果根节点的值相同,则递归地比较它们的左子树和右子树,判断左右子树是否相同。
递归调用:
- isSameTree(p.left, q.left) 递归地比较两棵树的左子树。
- isSameTree(p.right, q.right) 递归地比较两棵树的右子树。
- 最终,通过递归的方式,判断了整棵树的结构和节点值是否完全相同。
这段代码利用递归的思想,深度优先地比较了两棵二叉树的结构和节点值,判断它们是否相同。
3. 完整代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//首先判断根节点if((p == null && q != null) || (p != null && q == null)){//结构不一样return false;} //如果上面if语句没有走 说明 剩下两个都为空 或者 两个都不为空if(p == null && q == null){//说明两个为空return true;}if(p.val != q.val){return false;//说明根节点的值不一样}//以下就是根节点的值一样 判断 左右子树的值是否一样//利用递归return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
}
二、另一棵树的子树
写这一道题,要深入理解第一道题,因为要用到
527.另一棵树的子树
1. 题目
2. 解析(深度优先搜索暴力匹配)
- 从根节点开始判断,如果主树为空的话,则不可能包含子树
【isSubtree方法】
3. 完整代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null){return false;}if(isSametree(root,subRoot)){return true;}if(isSubtree(root.left,subRoot)){return true;}if(isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSametree(TreeNode p,TreeNode q){if((p != null && q == null) || (p == null && q != null)){return false;}if(p == null && q == null){return true;}if(p.val != q.val){return false;}return isSametree(p.left,q.left) && isSametree(p.right,q.right);}
}
4.深度优先搜索序列上做串匹配
class Solution {List<Integer> sOrder = new ArrayList<Integer>();List<Integer> tOrder = new ArrayList<Integer>();int maxElement, lNull, rNull;public boolean isSubtree(TreeNode s, TreeNode t) {maxElement = Integer.MIN_VALUE;getMaxElement(s);getMaxElement(t);lNull = maxElement + 1;rNull = maxElement + 2;getDfsOrder(s, sOrder);getDfsOrder(t, tOrder);return kmp();}public void getMaxElement(TreeNode t) {if (t == null) {return;}maxElement = Math.max(maxElement, t.val);getMaxElement(t.left);getMaxElement(t.right);}public void getDfsOrder(TreeNode t, List<Integer> tar) {if (t == null) {return;}tar.add(t.val);if (t.left != null) {getDfsOrder(t.left, tar);} else {tar.add(lNull);}if (t.right != null) {getDfsOrder(t.right, tar);} else {tar.add(rNull);}}public boolean kmp() {int sLen = sOrder.size(), tLen = tOrder.size();int[] fail = new int[tOrder.size()];Arrays.fill(fail, -1);for (int i = 1, j = -1; i < tLen; ++i) {while (j != -1 && !(tOrder.get(i).equals(tOrder.get(j + 1)))) {j = fail[j];}if (tOrder.get(i).equals(tOrder.get(j + 1))) {++j;}fail[i] = j;}for (int i = 0, j = -1; i < sLen; ++i) {while (j != -1 && !(sOrder.get(i).equals(tOrder.get(j + 1)))) {j = fail[j];}if (sOrder.get(i).equals(tOrder.get(j + 1))) {++j;}if (j == tLen - 1) {return true;}}return false;}
}
三、翻转二叉树
226.翻转二叉树
1.题目
2.解析(利用深度优先搜索)
- 首先要进行空树检查
- 进行单节点树检查
- 翻转操作:首先创建一个临时节点 tmp,将 root 的左右子树交换。这里直接交换了节点的引用,而不是交换节点的值。
- 递归地对 root 的左子树和右子树进行翻转操作。
- 返回经过翻转处理后的根节点 root
3.完整代码
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {//空树if(root == null){return null;}//只有一个节点的树if(root.left == null && root.right == null && root.val >= -100 && root.val <= 100){return root;}//定义一个中间结点TreeNode tmp = new TreeNode();tmp.left = root.left;tmp.right = root.right;root.left = tmp.right;root.right = tmp.left;invertTree(root.left);invertTree(root.right);return root;}
}
【改进后的代码】
class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 交换左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}
这个简化版本避免了使用额外的临时节点,并且更加清晰地表达了翻转操作
四、总结
将大问题划分成一个一个相同的小问题来求解,一定要注意判断条件
相关文章:
【leetcode】相同的树、另一棵树的子树、翻转二叉树(利用深度优先遍历)
Hi~!这里是奋斗的明志,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎 ~~ 🌱🌱个人主页:奋斗的明志 🌱🌱所属专栏:数据结构、LeetCode专栏 📚本系…...
Linux系统窗口水印难点分析
给应用程序加水印是保护数据的一种方式,window上可以通过给进程通过注入的方法给进程的窗口创建一个同大小的副窗口,在副窗口上绘制水印内容,同时设置副窗口透明同时透传事件,这样就可以达到在源窗口上显示水印的效果且不影响程序…...
LabVIEW与CANopen实现自动化生产线的设备控制与数据采集
在某工厂的自动化生产线上,多个设备通过CANopen网络进行通信和控制。这些设备包括传感器、执行器和PLC,它们共同负责监测和控制生产过程中的关键参数,如温度、压力、速度等。为了实现对整个生产线的集中监控和管理,工厂决定使用La…...
吃惊!这个Windows双系统方法逆天了|UEFI篇
前言 最近小白在折腾别的系统教程,偶然间发现居然有一个很nice的Windows双系统教程。于是于是,果断尝试了一下,发现真的很可行! 这个双系统的办法并不需要使用到WinPE系统,因此并不需要使用到U盘,只需要在…...
【C语言基础】C语言试题复习
1. 执行下面的程序段后,k 的值是_______。 int k1,n325; do { k*n%10;n/10;}while(n); 解析: 给定 n 325 和初始 k 1,代码中的循环将会进行如下操作: 第一次循环:n % 10 得到 5,因此 k * 5,即 k 1 * 5 …...
一拖三无线充底座-带给你极致的便利生活
随着科技的不断进步,无线充电技术已经逐渐渗透到我们日常生活的方方面面,一拖三无线充底座作为其中的佼佼者,以其高效、便捷的特点受到广大用户的青睐。本文将从电磁感应原理、多线圈设计、频率匹配、电能传输、功率分配以及充电管理六个方面…...
探索 Electron:打造深度书籍挖掘机的搜索体验
Electron是一个开源的桌面应用程序开发框架,它允许开发者使用Web技术(如 HTML、CSS 和 JavaScript)构建跨平台的桌面应用程序,它的出现极大地简化了桌面应用程序的开发流程,让更多的开发者能够利用已有的 Web 开发技能…...
tomato靶场
扫描网址端口 访问一下8888 我们用kali扫描一下目录 访问这个目录 产看iofo.php源码,发现里面有文件包含漏洞 访问/etc/passwd/发现确实有文件包含漏洞 远程连接2211端口 利用报错,向日志文件注入木马,利用文件包含漏洞访问日志文件 http:/…...
【Vue】computed计算对象不生效问题?
问题描述 最近使用vuex来管理全局状态,遇到了computed计算state中数据却不生效的问题。 原因分析: 先看vue官网示例: computed接收的是一个getter函数,但是这个getter函数是懒加载并且有缓存的,当计算属性最终计算…...
算法小白的进阶之路(力扣9~12)
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…...
DOCKER容器中安装JDK1. 8 详细步骤
1.通过查找JDK8的远程镜像 docker search jdk 2.选择一个远程镜像下载到本地仓库 #拉取镜像 docker pull kdvolder/jdk8#查看镜像 docker images 可以看到REPOSITORY列下面出现了kdvolder/jdk8 3.在docker容器中运行jdk8的镜像 docker run -di --namejdk1.8 kdvolder/jdk…...
计算机毕业设计Python+Tensorflow股票推荐系统 股票预测系统 股票可视化 股票数据分析 量化交易系统 股票爬虫 股票K线图 大数据毕业设计 AI
1、用pycharm打开项目,一定要打开包含manage.py文件所在文件夹 2、配置解释器:建议使用Anaconda(Python 3.8(base)),低于3.8版本的,页面会不兼容 3、安装依赖库:打开pycharm的终端,输入: pip in…...
深度学习常见的卷积和注意力机制文章集锦(持续更新)
卷积 友好链接1 卷积原理:几种常用的卷积(标准卷积、深度卷积、组卷积、扩展卷积、反卷积) 友好链接2 一文看尽深度学习中的20种卷积(附源码整理和论文解读) 友好链接3 深度学习中组卷积(Group convolution)、深度卷积…...
如何在立创EDA的PCB电路板导入logo图案
1、首先制作好logo图案,一般为公司logo图标,如下图 2、打开立创EDA的PCB文件,如下图 3、将PCB的图层切换到丝印层: 4、然后选择EDA菜单栏的放置---图片: 5、进入后点击选择图片,将logo图片导入,…...
springboot集成canal
目录 一、打开mysql的binlog1.1 打开 MySQL 配置文件 my.cnf(通常位于 /etc/mysql/my.cnf 或 /etc/my.cnf)并添加或修改以下设置:1.2 重启mysql服务1.3 验证是否生效 二、 部署canal 服务端(docker)2.1 下载启动脚本(可…...
leetcode数论(2447. 最大公因数等于 K 的子数组数目)
前言 经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。 描述 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。 子数组 是数组中一个连续的非空序列…...
实现数组扁平化的几种方式
目标: 实现数组扁平化[1,[2,[3,4,5]]] > [1,2,3,4,5] 我们有几种方法可以实现,分别为: 1、递归 function flatten(list){return list.reduce((tar, cur) > {if(Array.isArray(cur)){tar tar.concat(flatten(cur));} else {tar.push(cur);}return tar;}, []); } flatt…...
3D打印技术正悄然重塑模具工业格局
虽被誉为“工业之母”的模具在批量生产中仍占据核心地位,但3D打印以其“无模”直接成型的特性,在小批量、非标准化及复杂结构件制造领域展现出独特优势,随着技术和装备的不断发展,目前3D打印正逐渐向批量生产渗透,某品…...
深入解析 KMZ 文件的处理与可视化:从数据提取到地图展示项目实战
文章目录 1. KMZ 文件与 KML 文件简介1.1 KMZ 文件1.2 KML 文件 2. Python 环境配置与依赖安装3. 代码实现详解3.1 查找 KMZ 文件3.2 解压 KMZ 文件3.3 解析 KML 文件3.4 可视化 KMZ 数据 4. 项目实战4.1. 数据采集4.2. 项目完整代码 5. 项目运行与结果展示6. 总结与展望 在处理…...
YOLOv5轻量化改进 | backbone | 结合MobileNetV4(包含多个结构和使用方式)
YOLOv5轻量化改进 | backbone | 结合MobileNetV4(包含多个结构) 本文介绍论文原理介绍网络代码多种yaml设置网络测试及实验结果<!-- 这里放入论文图片 -->  ;本文介绍 本文给大家带来的改进机制是结合MobileNetV4骨干网络,其中来自2024.5月发布的MobileNetV4…...
学习安卓开发遇到的问题
问题1:学习禁用与恢复按钮中: java代码报错:报错代码是 R.id.btn_enable;case R.id.btn_disable;case R.id.btn_test: 代码如下:(实现功能在代码后面) package com.example.apptest;import static java.…...
数学建模--禁忌搜索
目录 算法基本原理 关键要素 应用实例 实现细节 python代码示例 总结 禁忌搜索算法在解决哪些具体类型的组合优化问题中最有效? 禁忌搜索算法的邻域结构设计有哪些最佳实践或案例研究? 如何动态更新禁忌表以提高禁忌搜索算法的效率和性能&#…...
LeetCode 第136场双周赛个人题解
Q1. 求出胜利玩家的数目 原题链接 Q1. 求出胜利玩家的数目 思路分析 直接模拟 时间复杂度:O(N) AC代码 class Solution { public:int winningPlayerCount(int n, vector<vector<int>>& pick) {unordered_map<int, unordered_map<int, …...
The operation was rejected by your operating system. code CERT_HAS_EXPIRED报错解决
各种报错,试了清缓存,使用管理员权限打开命令行工具,更新npm,都不好使 最终解决:删除 c:/user/admin/ .npmrc...
[Git][基本操作]详细讲解
目录 1.创建本地仓库2.配置 Git3.添加文件1.添加文件2.提交文件3.其他 && 说明 4.删除文件5.跟踪修改文件6.版本回退7.撤销修改0.前言1.未add2.已add,未commit3.已add,已commit 1.创建本地仓库 创建⼀个Git本地仓库:git init运行该命…...
springMVC中从Excel文件中导入导出数据
目录 1. 数据库展示2. 导入依赖3. 写方法3.1 导入数据3.2 导出数据 4. 效果5. 不足6. 参考链接 1. 数据库展示 2. 导入依赖 pom.xml <!--文件上传处理--><dependency><groupId>commons-io</groupId><artifactId>commons-io</artifactId>&…...
C++的STL简介(三)
目录 1.vector的模拟实现 1.1begin() 1.2end() 1.3打印信息 1.4 reserve() 1.5 size() 1.6 capacity() 1.7 push_back() 1.8[ ] 1.9 pop_back() 1.10 insert&…...
BERT模型
BERT模型是由谷歌团队于2019年提出的 Encoder-only 的 语言模型,发表于NLP顶会ACL上。原文题目为:《BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding》链接 在前大模型时代,BERT模型可以算是一个参数量比…...
举例说明计算机视觉(CV)技术的优势和挑战
计算机视觉(CV)技术是通过计算机模拟和处理图像与视频数据来模拟人类视觉的能力。它可以带来许多优势,也面临一些挑战。 优势: 自动化:CV技术可以自动处理大量的图像和视频数据,从而提高工作效率和准确性。…...
Animate软件基础:关于补间动画中的图层
Animate 文档中的每一个场景都可以包含任意数量的时间轴图层。使用图层和图层文件夹可组织动画序列的内容和分隔动画对象。在图层和文件夹中组织它们可防止它们在重叠时相互擦除、连接或分段。若要创建一次包含多个元件或文本字段的补间移动的动画,请将每个对象放置…...
顺企网浙江网站建设/短视频seo询盘获客系统软件
6月2日,华为发布了最新版的鸿蒙操作系统 HarmonyOS 2.0,以及一系列搭载鸿蒙的硬件产品,比如手机,手表,平板,耳机,显示器等等。如今的智能终端越来越多,厂商不可能为每个设备单独准备…...
合肥网站建设方案服务/图片识别 在线百度识图
如何部署你的网站?创建网站之前,需要做很多基础工作。首先最关键的第一步就是要学习如何部署网站。您需要知道如何部署网站,网站部署在哪个服务器上最适合您的需求,以及未来对网站的规划。服务器主机在其Web服务器上提供空间&…...
如何用wampp 做网站/2022搜索引擎
python3实现小球转动抽奖小游戏来源:中文源码网 浏览: 次 日期:2019年11月5日【下载文档: python3实现小球转动抽奖小游戏.txt 】(友情提示:右键点上行txt文档名->目标另存为)python3实现小球转动抽奖小游戏最近老师在讲 tkinter,所…...
html5 图片网站模板/百度识图软件
转载于:https://www.cnblogs.com/Minstrel223/p/10966959.html...
网站维护怎么做/青岛快速排名
1.跨平台需求显然,如果您的目标是拥有一个应该能够跨平台(Windows,Linux和MacOS)运行的应用程序(Web /服务),那么.NET生态系统中的最佳选择就是使用 . NET Core作为其运行时(CoreCLR)和库是跨平台的 . 另一种选择是使用Mono项目 . 这两种选择…...
网站建设中 html 下载/网络优化行业的发展前景
手机系统文件中的以下文件是不能删除的: 1、.android_secure:官方app2sd的产物,存储了相关的软件使用认证验证,删除之后SD卡中的软件将无法使用。 2、Android:存放重要的程序数据,比如google:…...