数据结构——二叉树经典习题讲解
各位看官早安午安晚安呀
如果您觉得这篇文章对您有帮助的话
欢迎您一键三连,小编尽全力做到更好
欢迎您分享给更多人哦
大家好,我们今天来学习java数据结构的二叉树
递归很重要的一些注意事项:
- 1:递归你能不能掌握在于:你能不能想清楚第一层非递归 以及 递归结束的条件(也就是最后一层递归,有时候递归结束的条件可能有好几个这很常见)(结束的条件仔细想一下是否能够合并呢?return root,return null,下一层root啥也没干,root == null,是否能够合并呢?这个其实无伤大雅,但是能合并尽量还是合并一下)(这两个场景你能够想清楚,你基本思路就没什么问题)
- 2:递归有返回值的
- 2.1:如果有返回值,你大概率是要接收你下一层递归的返回值()(然后你进行整理完之后继续向上返回)
- 2.2:递归如果返回值是要叠加的,譬如求二叉树的高度的,这个返回值一定要接收。
1.1.判断两个二叉树是否相等
链接
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;}return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}
1.2.相同的二叉树
相同的树
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;}return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(isSameTree(root,subRoot)){ //判断一开始就是否相等return true;}if(root == null){return false;}if(isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)){ //左边和右边一个相等就行//其实这个就是前序遍历,利用返回值return true;}return false;}
1.3.翻转二叉树
翻转二叉树
public TreeNode invertTree(TreeNode root) {if(root == null){return null;}//交换节点TreeNode tmp = root.left;root.left = root.right;root.right = tmp;//翻转invertTree(root.left);invertTree(root.right);return root;}

1.4.平衡二叉树
平衡二叉树
补充知识点:

//更改的平衡二叉树,因为我们在算高度的时候每一颗子树的高度我们都算过,我们完全可以算整个树的高度//然后进行顺带算两边的高度差是否 <= 1,一次性算完int getHeight2(TreeNode root){if(root == null){return 0;}//左树高度和右树高度int leftHeight = getHeight2(root.left);int rightHeight = getHeight2(root.right);//两边高度差<= 1并且都大于0(任何一个高度为-1的时候,整个树的返回值就为-1(-1代表不平衡))// 只要有一个-1返回,那么之后都是返回-1,不平衡if(Math.abs(leftHeight - rightHeight) <= 1 && leftHeight >= 0 && rightHeight >= 0){return Math.max(leftHeight,rightHeight)+1;}return -1;}public boolean isBalanced(TreeNode root) {if(root == null){return true;} return getHeight2(root) >= 0;}
1.5.对称二叉树
对称二叉树
public boolean isSymmetric(TreeNode root) {if(root == null){return true;}//我要看是否对称,肯定要两个节点进行比较,要两个变量return isSample(root.left,root.right);}public boolean isSample(TreeNode p , TreeNode q){//两边都是空的,就一个根,直接返回trueif( p == null && q == null){return true;}//一个为空另一个不为空,直接返回falseif( p == null || q == null){return false;}if(p.val != q.val){return false;}return isSample(p.left,q.right) && isSample(p.right,q.left);}

1.6.通过字符串构建二叉树
通过字符串构建二叉树
import java.util.Scanner;
class TreeNode{char val;TreeNode left;TreeNode right;public TreeNode(){}public TreeNode(char val){this.val = val;}
}// 注意类名必须为 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();//创建二叉树TreeNode root = create(str);//中序遍历inorder(root);}}public static int i = 0;public static TreeNode create(String str){ //递归的第一层要素就是要知道什么时候结束// 首先我们遇到 “#” 就要返回 ,但是我们的i还是要先++ 后返回if(str.charAt(i) == '#'){//但是我们要考虑的是,我们就算是返回了,我们的遍历str的i还是要往前走i++;return null;}else{TreeNode root = new TreeNode(str.charAt(i));i++;root.left = create(str);root.right = create(str);return root;}
//最后你会发现其实这两个返回值可以合并成一个,//其实每次递归题大家都可以看一下}//中序遍历public static void inorder(TreeNode root){if(root == null){return;}inorder(root.left);System.out.print(root.val +" ");inorder(root.right);}
}

1.7.二叉树分层遍历:
二叉树的层序遍历
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> list = new ArrayList<>();//别问 问就是OJ的测试用例让我这么干的// root = [] 预期结果[],所以下面返回的也是List而不是nullif(root == null){ //如果根节点都是null,就不用遍历了return list;}// 先把 根节点add进去队列里面Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);//tmp.add(root);//这里不对呀,最后一倍一倍的增长。这个size也不对,看我下面如何修改while(!queue.isEmpty()) {//int size = tmp.size();List<Integer> tmp = new ArrayList<>();//这个可不敢放在一开始呀,不然又叠加了(ArrayList好一点)int size = queue.size();//计算上一次add进来的总和, 下面直接就是 size!=0,这完全就是要把上一次的全poll出去while (size != 0) { //和上一个的区别就在于,上一个层序遍历是一个一个出队列的,这个是一次性把上一次add进来的全部poll出去TreeNode cur = queue.poll();tmp.add(cur.val);// System.out.println(cur.val + " ");size--;//记得--;if (cur.left != null) {queue.offer(cur.left);}if (cur.right != null) {queue.offer(cur.right);}}list.add(tmp);}return list;}

1.8.二叉树的最近公共祖先
二叉树的最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(p == root || q == root){return root;}if(root == null){return null;}TreeNode leftRoot = lowestCommonAncestor(root.left,p,q);TreeNode rightRoot = lowestCommonAncestor(root.right,p,q);if(leftRoot != null && rightRoot != null){return root;} else if (leftRoot != null) {return leftRoot;}else{return rightRoot;}}

解法二:看成两个链表相交,找相交点
private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode>stack){// 判断这个节点是不是这个路径上的节点(如果不是,看看它的左子树和右子树是不是这个路径上的节点如果都不是)//就返回false,把这个节点pop出来if(root == null || node == null){return false;}stack.push(root);//一定要压进去,不然root == node 导致这个栈里面没有了元素if(root == node){return true;}boolean flg1 = getPath(root.left,node,stack);//看看左节点有没有if(flg1){return true;}boolean flg2 = getPath(root.right,node,stack);//看看右节点有没有if(flg2){return true;}//都没有就return falsestack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {Stack<TreeNode>stack1 = new Stack<>();Stack<TreeNode>stack2 = new Stack<>();//利用getPath初始化这两个栈getPath(root,p,stack1);getPath(root,q,stack2);//初始化之后,进行比较,让长栈先走size步int size = stack1.size() -stack2.size();if(size > 0){while(size != 0){stack1.pop();size--;}}else{while(size != 0){stack2.pop();size++;}}while(!stack1.isEmpty() && ! stack2.isEmpty()){ //&&后面的写不写都行if(stack1.peek().equals(stack2.peek())){return stack1.peek();}stack1.pop();stack2.pop();}return null;}
1.9. 从前序与中序遍历序列构造二叉树
从前序与中序遍历序列构造二叉树
class Solution {public int preIndex;//一定要设置成成员变量(全局效果),局部变量的话放方法参数里,每次都是传值调用//不能保证preIndex一直往前走public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length -1);}private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){if(inbegin > inend ){ //其实这里的结束有两次,inbegin = inend 也应该结束(但是合并成一种情况了)return null;}if(inbegin == inend){int pre = preIndex;preIndex++;return new TreeNode(preorder[pre]);}//先看这个(前序遍历的)节点是否在中序遍历的这个范围内,在的话我再把这个根节点给创建出来int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);if(rootIndex == -1){return null;}TreeNode root = new TreeNode(preorder[preIndex]);preIndex++;root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inend);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key){for(int i = inbegin; i<= inend ; i++){if(inorder[i] == key){return i;}}return -1;}
}


1.10.从中序与后序遍历序列构造二叉树
如果后序:是先递归右树,再左树,再根(此刻的后序的字符串就是前序的逆转)
1从中序与后序遍历序列构造二叉树
class Solution {public int postIndex ;//一定要设置成成员变量(全局效果),局部变量的话放方法参数里,每次都是传值调用//不能保证preIndex一直往前走public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length -1;return buildTreeChild(postorder,inorder,0,inorder.length -1);}private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){if(inbegin > inend ){ //其实这里的结束有两次,inbegin = inend 也应该结束(但是合并成一种情况了)return null;}//先看这个(前序遍历的)节点是否在中序遍历的这个范围内,在的话我再把这个根节点给创建出来int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);if(rootIndex == -1){return null;}TreeNode root = new TreeNode(postorder[postIndex]);postIndex--;root.right = buildTreeChild(postorder,inorder,rootIndex + 1,inend);root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);return root;}private int findIndex(int[] inorder,int inbegin,int inend,int key){for(int i = inbegin; i<= inend ; i++){if(inorder[i] == key){return i;}}return -1;}
}
1.11.前序遍历二叉树(迭代实现)
public static void preOrder1(TreeNode root) {if (root == null) {return;}//本质上这还是递归的思想(stack还是往回走,不然你路上的节点,没办法遍历他的右边;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为,第一次stack是空的while (cur != null) {//一直往System.out.print(cur.val);stack.push(cur);cur = cur.left;//其实一开始我是这么想的/*if(cur == null){cur = stack.pop();cur = cur.right;//但是这样就废了呀,右边为空就完蛋了,循环结束,gameOver}*/}//左边为空,直接就拿回我上一个根,然后打印右边cur = stack.pop();cur = cur.right;}}
1.11.中序遍历二叉树(迭代实现)
public static void inOrder1(TreeNode root) {if (root == null) {return;}//本质上这还是递归的思想(stack还是往回走,不然你路上的节点,没办法遍历他的右边;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为,第一次stack是空的while (cur != null) {//一直往stack.push(cur);cur = cur.left;}//左边为空,直接就拿回我上一个根,然后打印右边cur = stack.pop();System.out.print(cur.val);cur = cur.right;}}
1.11.后序遍历二叉树(迭代实现)
//根据字符串循环进行后序遍历public static void postOrder1(TreeNode root) {if (root == null) {return;}//本质上这还是递归的思想(stack还是往回走,不然你路上的节点,没办法遍历他的右边;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;TreeNode top = null;while (cur != null || !stack.isEmpty()) {// 加个cur !=null,纯粹是因为,第一次stack是空的while (cur != null) {//一直往stack.push(cur);cur = cur.left;}//左边为空,直接就拿回我上一个根,然后打印右边top = stack.peek();if(top .right == null || top.right == prev){stack.pop();System.out.print(top.val + " ");prev = top;}else {// 右边不为空不能popcur = top.right;}}}
上述就是二叉树习题讲解的全部内容了,能看到这里相信您一定对小编的文章有了一定的认可,二叉树的出现让我们对于数据的组织的利用有了更加方便的使用~~
有什么问题欢迎各位大佬指出
欢迎各位大佬评论区留言修正
您的支持就是我最大的动力!!!!
相关文章:
数据结构——二叉树经典习题讲解
各位看官早安午安晚安呀 如果您觉得这篇文章对您有帮助的话 欢迎您一键三连,小编尽全力做到更好 欢迎您分享给更多人哦 大家好,我们今天来学习java数据结构的二叉树 递归很重要的一些注意事项: 1:递归你能不能掌握在于࿱…...
神经网络八股(三)
1.什么是梯度消失和梯度爆炸 梯度消失是指梯度在反向传播的过程中逐渐变小,最终趋近于零,这会导致靠前层的神经网络层权重参数更新缓慢,甚至不更新,学习不到有用的特征。 梯度爆炸是指梯度在方向传播过程中逐渐变大,…...
堆、优先队列、堆排序
堆: 定义: 必须是一个完全二叉树(完全二叉树:完全二叉树只允许最后一行不为满,且最后一行必须从左往右排序,最后一行元素之间不可以有间隔) 堆序性: 大根堆:每个父节点…...
vue 学习-vite api.js
/** 整机管理 * */ // 整机分类 列表 export const wholeMachineServersType params > ajaxGet({url: wholeMachine/serverstype/,params}) // 整机分类 新增 export const wholeMachineServersTypeAdd params > ajaxPost({url: wholeMachine/serverstype/,params}) /…...
java练习(35)
ps:题目来自力扣 整数反转 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。 假设环境不允许存储 64 位整数(有符号或无符号)…...
PW_Balance
目录 1、 PW_Balance 1.1、 getDocumentsTypeID 1.2、 getShouldAmount 1.3、 setOptimalAmount 1.4、 setRemark PW_Balance package com.gx.pojo; public class PW_Balance { private Integer BalanceID; private Integer PaymentID; private Integer ReceptionID…...
【Linux-网络】HTTP的清风与HTTPS的密语
🎬 个人主页:谁在夜里看海. 📖 个人专栏:《C系列》《Linux系列》《算法系列》 ⛰️ 道阻且长,行则将至 目录 📚 引言 📚 一、HTTP 📖 1.概述 📖 2.URL ǵ…...
【前端框架】vue2和vue3的区别详细介绍
Vue 3 作为 Vue 2 的迭代版本,在性能、语法、架构设计等多个维度均有显著的变革与优化。以下详细剖析二者的区别: 响应式系统 Vue 2 实现原理:基于 Object.defineProperty() 方法实现响应式。当一个 Vue 实例创建时,Vue 会遍历…...
CMake管理依赖实战:多仓库的无缝集成
随着软件复杂度的增加,单个项目可能需要依赖多个外部库或模块。这些依赖项可能是来自不同的代码仓库,如ATest和BTest。为了实现高效的依赖管理,CMake提供了多种方式来处理这种多仓库的情况。下面我们将详细介绍几种常见的方法,并通…...
Touchgfx 编写下载算法文件(.stldr)
一)下载算法文件主要参考官方的STM32 ST-LINK Utility模板:(文件所在位置如下:) C:\Program Files (x86)\STMicroelectronics\STM32 ST-LINK Utility\ST-LINK Utility\ExternalLoader\M25P64_STM3210E-EVAL\Project\MD…...
回不去的乌托邦
回不去的乌托邦 坐在电脑面前愣神间已至深夜,依然睡意不起。 相比于带着疲惫入睡,伏案发呆更令人惬意。想起最近在自媒体上看到的一句话“最顶级的享受变成了回不去的乌托邦”。 “这是兄弟们最后一次逛校园了,我拍个照”。我的记忆力总是用在…...
如何在 SpringBoot 项目使用 Redis 的 Pipeline 功能
本文是博主在批量存储聊天中用户状态和登陆信息到 Redis 缓存中时,使用到了 Pipeline 功能,并对此做出了整理。 一、Redis Pipeline 是什么 Redis 的 Pipeline 功能可以显著提升 Redis 操作的性能,性能提升的原因在于可以批量执行命令。当我…...
Linux----线程
一、基础概念对比 特性进程 (Process)线程 (Thread)资源分配资源分配的基本单位(独立地址空间)共享进程资源调度单位操作系统调度单位CPU调度的最小单位创建开销高(需复制父进程资源)低(共享进程资源)通信…...
实现rolabelimg对于dota格式文件的直接加载和保存
在本篇博客中,我们将讲解如何修改roLabelImg.py文件,使其能够直接加载和保存Dota格式的标注文件(txt)以替换掉复杂的xml文件。通过对源代码的修改,我们将实现支持加载并保存Dota格式标注数据,以便与roLabel…...
bboss v7.3.5来袭!新增异地灾备机制和Kerberos认证机制,助力企业数据安全
ETL & 流批一体化框架 bboss v7.3.5 发布,多源输出插件增加为特定输出插件设置记录过滤功能;Elasticsearch 客户端新增异地双中心灾备机制,提升框架高可用性;Elasticsearch client 和 http 微服务框架增加对 Kerberos 认证支持…...
华为昇腾服务器固件Firmware、驱动Drive、CANN各自的作用与联系?
文章目录 **1. 固件(Firmware)****2. 驱动(Driver)****3. CANN(Compute Architecture for Neural Networks)****三者关系****典型问题定位** 华为昇腾服务器的固件、驱动和CANN是支撑其AI计算能力的核心组件…...
MySQL 视图入门
一、什么是 MySQL 视图 1.1 视图的基本概念 在 MySQL 中,视图是一种虚拟表,它本身并不存储实际的数据,而是基于一个或多个真实表(基表)的查询结果集。可以把视图想象成是一个预定义好的查询语句的快捷方式。当你查询…...
算法很美笔记(Java)——动态规划
解重叠子问题(当前解用到了以前求过的解) 形式:记忆型递归或递推(dp) 动态规划本质是递推,核心是找到状态转移的方式,也就是填excel表时的逻辑(填的方式),而…...
C++ ——继承
体现的是代码复用的思想 1、子类继承父类,子类就拥有了父类的特性(成员方法和成员属性) 2、已存在的类被称为“基类”或者“父类”或者“超类”;新创建的类被称为“派生类”或者“子类” 注意: (1&#…...
LeetCode 热题 100 283. 移动零
LeetCode 热题 100 | 283. 移动零 大家好,今天我们来解决一道经典的算法题——移动零。这道题在LeetCode上被标记为简单难度,要求我们将数组中的所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。下面我将详细讲解解题思路,…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...


