Java中关于二叉树层序遍历深入了解
作者:bigsai 发布时间:2023-07-26 07:06:09
前言
大家好,我是bigsai,在数据结构与算法中,二叉树无论是考研、笔试都是非常高频的考点内容,在二叉树中,二叉树的遍历又是非常重要的知识点,今天给大家讲讲二叉树的层序遍历。
这部分很多人可能会但是需要注重一下细节。
前面介绍了二叉排序树的构造和基本方法的实现,遍历也是比较重要的一环,并且二叉树的层序遍历也是bfs的最简单情况,这里我就将二叉树的层序遍历以及常考问题给大家分享一下。
在了解二叉树的遍历之前,需要具备数据结构与算法有队列、递归、栈、二叉树,这些内容咱们前面都有讲过,有这方面知识欠缺的同学可以往前翻一翻看一看!
层序遍历
层序遍历,听名字也知道是按层遍历。一个节点有左右节点,按层处理就是当前层兄弟节点的优先级要大于子节点处理的优先级,所以就是要将子节点放到后面处理,这就适合队列这个数据结构用来存储。
对于队列,先进先出。从root节点push到队列,那么队列中先出来的顺序是第二层的左右(假设都有),第二层每个节点执行的时候按照左右顺序添加到队列,第三层的节点就会有序的放到最后面……按照这样的规则就能得到一个层序遍历的顺序。
实现的代码也很容易理解:
public int[] levelOrder(TreeNode root) {
int arr[]=new int[10000];
int index=0;
Queue<TreeNode>queue=new ArrayDeque<>();
if(root!=null)
queue.add(root);
while (!queue.isEmpty()){
TreeNode node=queue.poll();
arr[index++]= node.val;
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
return Arrays.copyOf(arr,index);
}
分层存储
但是在具体笔试他可能要求你分层存储,例如力扣的102二叉树的层序遍历,要求返回一个List<List<Integer>>
类型。
这种相比上面一个多了一层逻辑就是每一层数据放到一块,这个也很容易,最好想到的就是两个队列(容器)一层一层遍历存储,然后交替,但是两个队列(容器)的写法常常会被面试官嫌弃,很多面试官让你想想怎么不用两个容器实现?
不用双队列去枚举结果也很容易,重要的就是先记录队列大小size(当前层节点数量),然后执行size次数的枚举即可,具体代码为:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>>list=new ArrayList<List<Integer>>();
if(root==null)return list;
Queue<TreeNode>q1=new ArrayDeque<TreeNode>();
q1.add(root);
while (!q1.isEmpty()) {
int size=q1.size();
List<Integer>value=new ArrayList<Integer>();
for(int i=0;i<size;i++)
{
TreeNode pNode=q1.poll();
if(pNode.left!=null)
q1.add(pNode.left);
if(pNode.right!=null)
q1.add(pNode.right);
value.add(pNode.val);
}
list.add(value);
}
return list;
}
之字形打印
除了这个直接层序遍历,二叉树还有很高频的就是之字形遍历,例如剑指offer32和力扣103 二叉树的锯齿形层序遍历,它的题目要求为:
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
这道题虽然不是难题,但是有点绕,本来队列这玩意我们就要大脑想一下什么顺序,又出来一个之字形,属实增加的思维逻辑,有不少小伙伴反映当时面试官让手撕这道题,自己以前明明写过,但是太紧张自己给自己绕进去了!
其实这个问题也很容易转化,因为值只是存储,我们按照老样子去进行层序遍历,只不过在遍历时候通过当前层奇偶数来给它判断是从左往右存储到结果中还是从右往左放到结果中。当然,判断奇数偶数也很容易,可以用变量,也可以用结果List的size()都可。
个人实现的一个朴素代码为:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> value=new ArrayList<>();//存储到的最终结果
if(root==null)
return value;
int index=0;//判断
Queue<TreeNode>queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){
List<Integer>va=new ArrayList<>();//临时 用于存储到value中
int len=queue.size();//当前层的数量
for(int i=0;i<len;i++){
TreeNode node=queue.poll();
if(index%2==0)
va.add(node.val);
else
va.add(0,node.val);
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
value.add(va);
index++;
}
return value;
}
上面实现代码也仅使用一个队列,不过这个问题可能有很多更巧妙的解法需要大家自己去挖掘。
来源:https://www.cnblogs.com/bigsai/p/15293058.html
猜你喜欢
- java引用传递的三种类型我这里使用了mldn视频里的例子,只用于学习交流。第一种结果:调用前:50调用后:1000分析:理解:好理解第二种
- (注意:本文基于JDK1.8) 前言包括迭代器中的remove()方法,以及删除单个元素、删除多个元素、删除所有元素、删除不包含的
- 方法重载概述方法重载指同一个类中定义的多个方法之间的关系,满足下列条件的多个方法互相构成重载* 多个方法在同一个类中* 多个放方法具有相同方
- 本文实例分析了Java接口默认方法带来的问题。分享给大家供大家参考,具体如下:一 点睛Java 8中,如果一个类实现两个或多个接口,即“变相
- * 其实就是java.lang.reflect.Proxy类动态的根据您指定的所有接口生成一个class byte,该class会继承P
- 其实这个表示有点不太对,应该是 Druid 动态切换数据源的方法,只是应用在了 springboot 框架中,准备代码准备了半天,之前在一次
- 一.以springboot为例,建立代码1.IExecCommandServer:public interface IExecCommand
- 前言我们在学习Windows应用程序开发中,经常会用到消息对话框给用户或者管理员一些的消息提示,它们都是基于对MessageBox类的消息对
- 本节我们来探讨如何使用Feign构造多参数的请求。笔者以GET以及POST方法的请求为例进行讲解,其他方法(例如DELETE、PUT等)的请
- 本文实例讲述了java字符串相似度算法。分享给大家供大家参考。具体实现方法如下:public class Levenshtein {&nbs
- 1.引言在开发中,拖放是一种比较常见的手势操作,使用它能够让应用的交互更加地便捷和友好,本文将简要介绍如何为Android中的View添加拖
- 前言 短时间提升自己最快的手段就是背面试题,最近总结了Java常用的面试题,分享给大家,希望大家都能圆梦大厂,加油,我命由我不由天
- 本文实例为大家分享了Android九宫格图片展示的具体代码,供大家参考,具体内容如下1.RandomAccessFileRandomAcce
- Java语言是SUN(Stanford University Network,斯坦福大学网络公司)公司1995年推出的一门高级编程语言,起初
- Android Studio 在引用外部依赖时,发现一直无法引用外部依赖。刚开始以为是墙的问题,尝试修改Gradle配置,未解决问题。最终发
- 本文实例为大家分享了Android自定义Banner轮播效果展示的具体代码,供大家参考,具体内容如下自定义View布局<Relativ
- Mapper 就是“映射”的意思,Mapper 文件时 Mybatis 中的 SQL 语句的配置文件
- 部署到webapps目录启动本文使用的Spring版本为Spring6,SpringBoot版本为3,JDK为17,可能会和之前有细微不同,
- 概述JavaScript是目前web开发中不可缺少的脚本语言,js不需要编译即可运行,运行在客户端,需要通过浏览器来解析执行JavaScri
- 这篇文章主要介绍了spring cloud gateway请求跨域问题解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定