二叉树相关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…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...