二叉树相关OJ题 — 第一弹
目录
1. 检验两棵树是否相同
编辑 1. 题目解析
2. 解题步骤
2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树
1. 题目解析
2. 解题步骤
3. 翻转二叉树
1. 题目解析
2.解题步骤
4. 判断一颗二叉树是否是平衡二叉树
1. 题目解析
2. 解题步骤
5. 对称二叉树
1.题目解析
编辑 2.解题步骤
6.二叉搜索树与双向链表
1.题目描述
2.解题思路
编辑
3.解题步骤:
7. 二叉树的构建及遍历
1.题目解析
2.解题思路编辑
3.解题步骤
4. 完整代码
1. 检验两棵树是否相同
1. 题目解析
两棵树相同的条件:两棵树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例2:
根节点相同,但是一个只有左树,一个只有右树,所以这两棵二叉树的结构不相同,因此这两棵树不是相同的二叉树 ;
示例3:
结构相同,节点值不同,所以不是相同的二叉树 。
同时遍历两棵树,先判断两棵树结构是否相同,如果结构相同,再判断两棵树的节点值是否相同
出现左边的两种情况,则说明两棵树结构不相同;出现右边两种情况,则说明两棵树的结构相同。
- 我们再更进一步,通过递归,同时遍历两棵树的每一个节点;遍历到的节点,会出现上图的四种情况;
只有当前遍历节点出现右边的两种情况,才能继续判断这两个节点的值是否相同;
只有节点的结构和值同时相同,我们才可以认为当前遍历的两个节点在两棵二叉树的相同位置,且值相同;
只有所有节点相同,才可以认为两棵树相同。
2. 解题步骤
假设 p,q 两个根节点所在的二叉树的节点个数分别为m,n;
则 isSameTree() 的时间复杂度为 O( min(m,n) ) 。
2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树
(通过上图题目中,提示的 root 和 subroot 的范围,说明root 和 subroot ,有可能是两棵相同的二叉树,并且 root 和 subroot 都不可能是一棵空树)
1. 题目解析
我们需要特别注意一下示例二,示例二这种情况,subroot 不是 root 的子树:
所以,我们通过前序遍历,遍历 root 和subroot ,判断:
1.当前 subroot 和 root 是否相同?
2.判断 subroot 和当前 root 的左子树相同?
3.判断 subroot 和当前 root 的右子树相同?
通过上面的判断,我们可以利用刚刚写的isSameTree() ,来判断当前递归遍历的 root 所代表的节点的树,和 subroot 树是否相同
2. 解题步骤
假设 root 和subroot 所代表的二叉树的节点个数分别为 r,s ;那么isSubtree() 的时间复杂度为O(r*s)。
3. 翻转二叉树
1. 题目解析
解决这一题,我们只需要每次递归的时候,如果当前递归的树是一棵空树,则不用翻转;否则,将左右节点的位置互换,即可达到翻转的效果 。
2.解题步骤
最好在处理一下,root是叶子节点的情况,以减少递归次数,优化消耗内存分布:
4. 判断一颗二叉树是否是平衡二叉树
1. 题目解析
平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1;
对于这道题,如果我们需要从下往上依次判断,当前root的所有节点的左右子树的深度是否相差不超过 1
2. 解题步骤
当前节点的左右子树高度差不超过1 && 递归左节点的子树为true && 递归右节点的子树为true
比较两种情况,就能发现:
图二return true的条件,必须是root,root.left,root.right三个节点的左右树高度差不超过1;
图一仅仅只是root的左右子树高度差不超过1
5. 对称二叉树
1.题目解析
下图左边的二叉树,结构一致,但是值不同,所以左边的二叉树不是轴对称二叉树:
2.解题步骤
6.二叉搜索树与双向链表
1.题目描述
2.解题思路
1.我们观察二叉搜索树和链表,可以发现,链表节点的顺序,就是二叉搜索树通过中序遍历得到的节点顺序。
(小知识:中序遍历遍历二叉搜索树,得到的顺序就是二叉树所有节点从小到大的排序)
所以,在接下来的做题中,我们要先模拟实现一个中序遍历的方法
2. 对于双向链表,每一个节点都会有 val,prev,next三个域;怎么确定每一个二叉树节点,转换成链表节点时的 prev域,next域,也是一个重要的难点。
因为是用二叉树模拟链表,所以我们用二叉树节点的 left 模拟 prev 域,用 right 模拟 next 域
3.解题步骤:
先模拟实现一个中序遍历的方法
此时,我们需要对 1节点 进行修改,让 root.left=null,root.right=2节点;
并且,我们在写完对当前root的调整后,程序会走到下一行,对root.right进行递归的代码,此时,root.left又一次被修改成null,相当于写死了,这个问题我们又该怎么改进呢?
改进方法很巧妙,先在方法外设置prev=null,把1节点设置为prev,再改变prev,让perv指向root,后续进行下一行的递归时,中序遍历到的节点就被一 一串联起来。
根据上图,我们已经把二叉树各个节点该如何调整指向的几步代码写好了;
我们可以以二叉树root遍历到 2节点为例子,就会发现:
1节点和2节点的双向关系已经确定好了,并且prev从1节点走到2节点,为下一次递归为2节点和3节点构建关系打下基础。
所以,我们需要处理一下边界情况:
因为 ConvertChild() 方法仅仅只是把二叉树调整成链表,在 Convert() 方法中,才会返回链表头节点,所以我们可以优化一下,将ConvertChild() 方法的返回值类型修改成 void:
根据代码,将二叉树被转换成链表的过程中,节点指向的调整过程,再仔细地思考一遍。当我们能想明白,上面用中序遍历的顺序,来调整每个节点的指向;并且想清楚调整的方式,就会为之拍案叫绝!
完善Convert() 即可。
7. 二叉树的构建及遍历
1.题目解析
小知识:
如果在遍历二叉树得到的输出结果,没有标出空树的具体位置,是无法通过前序遍历和后序遍历的输出结构还原一棵二叉树的;
题中提供的前序遍历输出结构已经标明空树的位置,我们可以提供输出结果还原二叉树
2.解题思路
3.解题步骤
4. 完整代码
import java.util.Scanner;class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}
//我们需要自己定义TreeNode类// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();Main s = new Main();//createTree() 的返回值是创建好二叉树后的头节点,用root接收一下TreeNode root = s.createTree(str);//将root传入inorderTree(),通过中序遍历遍历二叉树,打印节点inorderTree(root);}}//在被static修饰的静态方法中,无法调用成员变量public int i = 0;//创建二叉树public TreeNode createTree(String str) {//如果要通过递归,来拼接字符串,则不需要写循环,i的值通过递归来改变//那么i在下一次递归应该等于上一次递归的值TreeNode root = null;if (str.charAt(i) != '#') {//字符一定要有''root = new TreeNode(str.charAt(i));//分割的字符作为参数,来实例化节点//每次递归,都要通过i++,向后切割stri++;//通过递归拼接节点root.left = createTree(str);root.right = createTree(str);} else {i++;//遍历到的字符为'#',直接跳过}return root;}//中序遍历打印创建好的二叉树public static void inorderTree(TreeNode root) {if (root == null)return;inorderTree(root.left);System.out.print(root.val + " ");inorderTree(root.right);}
}
相关文章:

二叉树相关OJ题 — 第一弹
目录 1. 检验两棵树是否相同 编辑 1. 题目解析 2. 解题步骤 2.判断一棵大树中是否包含有和一棵小树具有相同结构和节点值的子树 1. 题目解析 2. 解题步骤 3. 翻转二叉树 1. 题目解析 2.解题步骤 4. 判断一颗二叉树是否是平衡二叉树 1. 题目解析 2. 解题步骤…...
【学习笔记】RFID
RFID 1、 概述 1.1、RFID 介绍 1.2、RFID 发展史 1.3、RFID 系统的构造 1.3.1、阅读器 Reader 和 天线 Antenna 1.3.3、电子标签 tag 1.4、电子标签按吐字率分类 1.5、电子标签按能量供应的方式划分 1.6、RFID 工作流程 …...

自动化部署-01-jenkins安装
文章目录 前言一、下载安装二、启动三、问题3.1 jdk版本问题3.2 端口冲突3.3 库文件加载问题3.4 系统字体配置问题 四、再次启动五、配置jenkins5.1 解锁5.2 安装插件5.3 创建管理员用户5.4 实例配置5.5 开始使用5.6 完成 总结 前言 spingcloud微服务等每次部署到服务器上&…...

AI工具大爆发,建议每个都使用收藏
2024年被誉为AI应用元年,这一年人们普遍意识到,未来占据主导地位的将是基于大模型的应用程序,而不仅仅是大模型本身。因此,在这一趋势的推动下,各式各样的AI应用如雨后春笋般涌现出来。 今天就聊聊这些好用的AI工具&a…...
Mybatis之参数处理
在MyBatis中,参数处理是非常关键的部分,它负责将传入的参数正确映射到SQL语句中 单个简单类型参数 简单类型对于mybatis来说都是可以自动类型识别的: 也就是说对于mybatis来说,它是可以自动推断出ps.setXxxx()方法的。ps.setSt…...

windows内核探索--打印windows的GDT表(全局描述符表)
x86 #include <windows.h> #include<stdio.h> #include "x86struct.h" void PrintSegmentDescriptor(ULONG64* sd, WORD Count); SegmentSelector GetSegmentSelector(USHORT Selector); int main() {printf("0环cs段寄存器 ");GetSegmentSel…...
【ChatGPT】让ChatGPT帮助进行头脑风暴与创意生成
让ChatGPT帮助进行头脑风暴与创意生成 在日常工作和生活中,创意和头脑风暴是解决问题、创新和推动项目的关键步骤。ChatGPT,作为一个强大的语言模型,不仅可以提供信息和答案,还可以成为强大的头脑风暴工具,帮助用户快…...

大数据处理随堂测试
HDFS MapReduce HBase Spark...

2024最新pycharm安装教程及基本使用(超详细,新手小白必看)
文章目录 前言一、官网下载二、安装步骤三、使用示范四、番外篇(汉)大纲 PythonPyCharm安装包领取方式戳‘这块里’ 前言 一、官网下载 1. 进入pycharm官网,点击下载 PyCharm: The Python IDE for data science and web development by J…...
三国杀钓鱼自动化
三国杀钓鱼脚本 前言 本来是想做必杀的,但是后来测试了大约400钓发现纯靠连点没有漏掉的鱼,所以必杀功能就舍弃了。 我pyinstaller打包后运行.exe居然黑屏了???可能是多进程报错处理没写好,反正还是用vsc…...

在pycharm中使用sqllite
在pycharm中使用sqllite sqllite 简介 SQLite 是一个开源的、轻量级的、关系型数据库管理系统(RDBMS),它设计用于嵌入到应用程序中,并且可以在无需外部服务器进程的情况下运行。SQLite 提供了完整的 SQL 语言支持,允…...

Linux——文件操作
前言 1)在Linux下面,一切皆文件,文件文件内容文件属性 2)在访问文件是,都得先将文件打开,修改文件的本质其实还是通过执行代码的形式修改。 3)文件是被进程打开的,一个进程可以打…...

数据结构 ——— 数组栈oj题:有效括号
目录 题目要求 代码实现 题目要求 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每…...

Character AI被起诉!14岁青少年自杀,AI陪伴何去何从
终于,AI在青少年心理问题方面,被推上了风口浪尖。 最近,美国佛罗里达州,一名14岁男孩Sewell Setzer的父母控告Character AI公司,声称孩子沉迷该公司的AI聊天机器人,最后走上了自杀的道路。 跟AI聊天还能致…...

CSS3 动画相关属性实例大全(三)(columns、filter、flex、flex-basis 、flex-grow、flex-shrink属性)
CSS3 动画相关属性实例大全(三) (columns、filter、flex、flex-basis 、flex-grow、flex-shrink属性) 本文目录: 一、columns属性(设置元素的列宽和列数) 二、filter属性(调整图像、背景和边…...

中国最厉害的思想家改名大师颜廷利:以诚信为基,塑企业信誉
跨文化融合,共筑包容性文化殿堂。尊重差异,促进团队合作,以诚信为基,塑企业信誉。融合《升命学说》智慧,推动员工多元化,践行社会责任,树立良好形象。创新不息,持续学习,…...
Python 代码实现用于进行水质模拟和优化加氯量
# -*- coding:utf-8 -*- import epamodule as em import epanetmsxmodule as msx import pandas as pd import numpy as np# 水质模拟,会产生一个rpt文件,但并不是返回这个文件。 def quality_simulation(inp_file,rpt_file,msx_file...

挖矿病毒来势汹汹
病毒来了, 我的个人站点使用了 wordpress, 它的不知哪个漏洞让黑客攻入了我的站点 使用 top 命令看到了有不明进程始终占据了 100% 的 CPU snapshot 1 snapshot 2 通过以下 "三板斧"可以查杀这个进程 先用 top (shiftp) 查找占据 CPU 最多的进程根据其进程号 pid 查看…...

国产数据库的蓝海在哪?
昨天有幸参加了 OceanBase2024年度发布会。在过去的几年中,OB 作为国内自主研发的分布式数据库,取得了令人瞩目的成就,特别是在金融行业,OB 通过不断的技术革新和优化,已经成为行业的领导者之一。OceanBase 展现了强大…...

MySQL~表的操作(创建表,查看表,修改表,删除表)
1.创建表 1.1.创建表 首先要选择需要操作的数据库,USE 数据库名,后续可以根据实际情况操作时添加。 USE fruitsales;建表语法: create table 表名( 字段名1 数据类型, 字段名2 数据类型, ); 实例:创建fruit_bak1表。 create t…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...