实例解析二叉树的层序遍历

二叉树的层序遍历，顾名思义，就是从左到右一层一层的去遍历二叉树。而每一层一层的遍历都和左右节点有着很大的关系。也就是我们选用的数据结构不能一股脑的往一个方向钻，而左右应该均衡考虑。这样我们就选用队列来实现。

我们先来看一个简单的二叉树的层序遍历的例子：

给定二叉树: [3,9,20,null,null,15,7],

3

   / \

  9  20

    /  \

   15   7

返回其层次遍历结果：

[

  [3],

  [9,20],

  [15,7]

]

我们根据给出的信息总结一下例题：给定一棵二叉树，把这棵二叉树一层一层地访问一遍，并且存储在一个二维数组里面。

这里面的难点就是怎么做到每次取一层的元素。

我们考虑使用队列来存储每一层的元素。为什么使用队列呢？因为对同一层的节点，先访问，再把他们存储到一个数组里，存储的顺序要和访问的顺序一致，而队列的特点就是先进先出，和我们的要求一致，所以考虑使用队列来实现本题。

算法如下：

1.首先，我们创建一个队列，用来访问节点（不一定是同一层）；创建一个列表，用来存储同一层的节点；创建一个二维列表，用来存储最终的答案。

2.然后，先对根节点做处理，把根节点加入队列，用列表存储，在二维列表里面加入刚才的列表，这样，第一层节点就存储好了。

3.到了第二层，我们再创建一个列表，用来存储第二层的节点，并获取一下队列的长度，这里队列的长度是多少，接下来就要进行几次循环，每次循环是访问并存储当前节点的左子节点和右子节点。

4.每次循环要做的工作是：弹出队列头部的一个节点，将这个节点的左子节点和右子节点加入队列，并且把左子节点和右子节点的值存进刚才的列表。

5.若干次循环完成后，队列里面就都是下一层的节点，列表已经存好了这一层的节点。

6.把列表加入二维列表。

7.重复第3~6步，直到队列为空。

对于队列，现进先出。从根节点的节点push到队列，那么队列中先出来的顺序是第二层的左右(假设有)。第二层每个执行的时候添加到队列，那么添加的所有节点都在第二层后面。

同理，假设开始pop遍历第n层的节点，每个节点会push左右两个节点进去。但是队列先进先出。它会放到队尾(下一层)。直到第n层的最后一个pop出来，第n+1层的还在队列中整齐排着。这就达到一个层序的效果。

实现代码如下：

public List<List<Integer>> levelOrder (TreeNode root) {

    Queue<TreeNode> q = new LinkedList<>();

    List<List<Integer>> ans = new ArrayList<>();

    List<Integer> list = new ArrayList<>();

    if (root == null)

        return ans;

    ((LinkedList<TreeNode>) q).add(root);

    list.add(root.val);

    ans.add(list);

    while (q.size() > 0) {

        list = new ArrayList<Integer>();

        int s = q.size();

        for (int i = 0; i < s; i++) {

            TreeNode tn = q.remove();

            if (tn.left != null) ((LinkedList<TreeNode>) q).add(tn.left);

            if (tn.right != null) ((LinkedList<TreeNode>) q).add(tn.right);

            if (tn.left != null) list.add(tn.left.val);

            if (tn.right != null) list.add(tn.right.val);

        }

        if (list.size() > 0) {

            ans.add(list);

        }

    }

    return ans;

}

我们需要注意的是，在第12行，一定要用一个整形数来存队列的大小，不能直接在循环条件里面使用i<q.size()，因为在循环体中，队列大小是会变的，所以有必要用一个数来“固定”住这一层的队列的长度。

二叉树的层序遍历只是二叉树的遍历方式中的一种，还有诸如前序遍历、中序遍历、后序遍历等等遍历方式。每一种遍历方式都值得单独拿出来好好说道，当然我们就不一一介绍了，感兴趣的小伙伴可以在本站的数据结构和算法教程里一一学习，都有很详细的讲解。