Java中关于二叉树层序遍历深入了解
前言
大家好,我是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; }
上面实现代码也仅使用一个队列,不过这个问题可能有很多更巧妙的解法需要大家自己去挖掘。
结语
二叉树的层序遍历是二叉树内容中较为简单的内容,但是层序遍历尤其是之字形遍历(锯齿形遍历)出现的频率真的太高了,并且最好是掌握比较好的方法不要显得太臃肿。
不过在实际遇到问题时候,能AC是第一位,然后才是精简的逻辑和骚气的代码。
二叉树层序遍历变种问题不多,掌握上面三个问题基本就够了,而二叉树的前序、中序、后序遍历(递归非递归)考察非常多,后面会给大家加快梳理总结,敬请期待!
到此这篇关于Java中关于二叉树层序遍历深入了解的文章就介绍到这了,更多相关Java 二叉树层序遍历内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13