二叉树的层序遍历，就考这么多！

前言

大家好，我是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>