二叉树的层序遍历是BFS的一种体现，但遇到的题中往往需要按层进行操作，也就是说需要记录每个元素属于哪一行。LeetCode中有相关的题目：LeetCode102、LeetCode199。鉴于在这一点上踩过坑，特此总结如下几种按层遍历的方法:
一、双指针
通常，我们都是创建一个队列，然后将根节点root放入队列中，然后以队列不为空作为while循环的条件进行遍历。在循环体中，每次从队列中弹出一个节点，然后判断该节点的左右孩子是否为null，不为null则将其放入队列中。
双指针的大概流程如下：指针last指向上一层的最后一个节点，指针nlast随着向队列中添加的节点变化，令cur指针指向当前弹出的节点。在向队列中添加节点时，判断cur是否等于last，即当前弹出的节点是否等于上一层的最后一个节点。如果是，则将last更新为nlast。这是因为nlast是随着添加节点变化的，而添加的节点是cur的孩子，如果此时的cur等于last，说明此时添加的节点是上一层的最后一个节点的孩子，也就是本层的最后的节点。
做动态图比较麻烦，时间并不是很充裕，因此只能文字说明。结合如下代码可能会更容易理解：
复制代码
1
2
3
4
5public List<List<Integer>> printByLayer(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if(root == null) return res; //记得判断输入为null的时候 Queue<TreeNode> queue = new LinkedList<
最后
以上就是鲜艳花瓣最近收集整理的关于二叉树层序遍历的几种方法(Java)的全部内容，更多相关二叉树层序遍历内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复