二叉树层序遍历的几种方法(Java)

二叉树的层序遍历是BFS的一种体现，但遇到的题中往往需要按层进行操作，也就是说需要记录每个元素属于哪一行。LeetCode中有相关的题目：LeetCode102、LeetCode199。鉴于在这一点上踩过坑，特此总结如下几种按层遍历的方法:

一、双指针

通常，我们都是创建一个队列，然后将根节点root放入队列中，然后以队列不为空作为while循环的条件进行遍历。在循环体中，每次从队列中弹出一个节点，然后判断该节点的左右孩子是否为null，不为null则将其放入队列中。
双指针的大概流程如下：指针last指向上一层的最后一个节点，指针nlast随着向队列中添加的节点变化，令cur指针指向当前弹出的节点。在向队列中添加节点时，判断cur是否等于last，即当前弹出的节点是否等于上一层的最后一个节点。如果是，则将last更新为nlast。这是因为nlast是随着添加节点变化的，而添加的节点是cur的孩子，如果此时的cur等于last，说明此时添加的节点是上一层的最后一个节点的孩子，也就是本层的最后的节点。
做动态图比较麻烦，时间并不是很充裕，因此只能文字说明。结合如下代码可能会更容易理解：

public List<List<Integer>> printByLayer(TreeNode root) {
   
	List<List<Integer>> res = new ArrayList<>();
	if(root == null) return res;	//记得判断输入为null的时候
	Queue<TreeNode> queue = new LinkedList<

最后

以上就是鲜艳花瓣为你收集整理的二叉树层序遍历的几种方法(Java)的全部内容，希望文章能够帮你解决二叉树层序遍历的几种方法(Java)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。