题解 | #求二叉树的层序遍历#

求二叉树的层序遍历

https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3

二叉树的层序遍历又名广度优先遍历,特点是从上到下,从左到右遍历。

此题的解法有两种,一是使用队列,二是使用递归。

一开始我用的是递归,因为之前做深度优先遍历的时候习惯了,但递归的做法稍微麻烦,需要使用TreeMap保存每层的数值和下标index标记层数。这里重点注意一定要用TreeMap,因为我们需要有序的输出每层结果,如果用HashMap的话,当结果的长度超过一定大小就会乱序,导致答案错误,这是我自己踩过的一个小小的坑。

队列的解法是推荐解法,我也是看了题解才知道原来用队列这么简单。就是一个whle循环和一个for循环就能解决。最外层的while循环是判断队列是否为空,不为空就继续遍历队列。for循环则是把这一层的所有节点拿到,注意关键点就在for循环这一步,循环开始之前一定要先拿到队列的size,这样可以才保证循环是在一层一层的进行而不会遍历到其它层。然后for循环遍历的同时把左右子节点再存进队列,这里是利用了队列的先进先出特点,因为size限定的原因,我们只会遍历某一层,同时又把下一层的节点给加上了。

#在线刷题#
全部评论

相关推荐

买蜜雪也用卷:我觉得应该没有哪个人敢说自己熟练使用git,代码分支一复杂还是得慢慢寻思一下的,不过基本的拉代码提交代码还有分支什么的是应该会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务