🍓1.什么是层序遍历？
层序遍历顾名思义就是按照二叉树的层数从左到右一层一层遍历数组。这种遍历方式和之前的三种前中序遍历都不太一样，如果你还对于前中后序三种遍历不太熟练，推荐你看一下我的这篇博客——二叉树的前中后序遍历（递归与迭代）。前中后序的遍历主要的区别是在于根节点与左右子结点的遍历顺序，而层序遍历则没有这个关系。
想完成层序遍历需要借用一个辅助数据结构队列来实现。为什么呢？因为队列的性质是先进先出，这非常符合我们的需求，因为层序遍历应用的正是图论中的广度优先搜索思想，只不过我们将该种思想应用与二叉树中。
https://ucc.alicdn.com/images/user-upload-01/3583e35d285f45359a789df7a607267c.gif
🍓2.化身叶问一打十
👊1.二叉树的层序遍历（图解加代码模板）
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
题目链接：二叉树的层序遍历https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
题目要求正是要求完成基础的层序遍历。
大家要注意这几个点：
Queue里的泛型类型的TreeNode而不是Integer，它的功能是辅助我们让节点按照我们想要的顺序去排列
在while(!queue.isEmpty())前需要先把头结点放入队列，否则循环根本就无法进入了，这个循环判断的是整棵树是否被遍历完。
while(len-->0)是每一层遍历的起点，所以path是用来记录每一层的元素，遍历结束后它会被赋值一份放入到答案数组list中，而每次遍历开始时都会有一个新的path
len变量是用来区分二叉树的每一层级的
class Solution { //用来存放答案数组 List<List<Integer>> list=new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { if(root==null) return list; bfs(root); return list; } public void bfs(TreeNode root){ //辅助队列帮忙完成层序遍历 Queue<TreeNode> queue=new LinkedList<>(); //1.注意先要把头结点放进去，否则队列就为空了 queue.offer(root); while(!queue.isEmpty()){ //2.每一个path是用来遍历二叉树的每一层的 List<Integer> path=new ArrayList(); //len是当前队列的长度，也是我们即将遍历的一层的元素个数 //len属性可以帮助我们去区分层与层之间 int len=queue.size(); while(len-->0){ //从队里弹一个元素 TreeNode node=queue.poll(); //用path记录下值 path.add(node.val); //将非空的左右子结点加入队列 if(node.left!=null) queue.offer(node.left); if(node.right!=null) queue.offer(node.right); } //走到这一步说明我们遍历完了一层，将记录下这层的path加入到我们的答案中 list.add(new ArrayList(path)); } } }
https://ucc.alicdn.com/images/user-upload-01/3b3a0da2f80245c99c7c676ae67426cc.gif
👊2.二叉树的层序遍历||
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
题目链接：二叉树的层序遍历||https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
这题和第一题的要求其实一样，只不过变成了从底向上层序遍历输入而已。难道我们真的从底向上层序遍历？当然不用，我们只需要把在上面的代码上改动一个地方即可，就是让每次把答案数组path加入到list的第一个位置也就是0下标处，这样就可以完成自底向上的层序遍历。
class Solution { List<List<Integer>> list=new ArrayList<>(); //当然两道题的函数名不同 public List<List<Integer>> levelOrderBottom(TreeNode root) { if(root==null) return list; bfs(root); return list; } public void bfs(TreeNode root){ Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> path=new ArrayList(); int len=queue.size(); while(len-->0){ TreeNode node=queue.poll(); path.add(node.val); if(node.left!=null) queue.offer(node.left); if(node.right!=null) queue.offer(node.right); } //与第一道题唯一区别的地方 list.add(0,new ArrayList(path)); } } }
