数据结构和算法基础篇（十二）二叉树层次遍历

         前面几篇文章介绍了二叉树的前序遍历、中序遍历和后续遍历。这里面我们使用了递归版本的实现和非递归版本的实现。递归版本的实现是比较简单的，非递归版本的实现就有点难度了，但是这正是提高我们能力的机会。

       今天我们介绍二叉树最后一种遍历方式，层次遍历。

    我们以Leetcode上的题目来讲解。

102. Binary Tree Level Order Traversal    

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7]
,

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

       题目的意思，给定一个二叉树，要求我们按照每一层进行遍历。得到的结果就是每一层的元素集合。

    思路就是，我们通过根节点，将根节点3加入队列中。当前队列节点个数为1，那么这一层就一个元素3。然后将根节点3的左右节点9和20加入队列，这时候队列节点个树就是2个。第二次遍历队列，取两次，每次取出的时候将自己节点的左右节点加入队列中。

      详细过程如下：

（1）将根节点加入队列，队列长度为1。

（2）从队列中取1次数据，同时将该元素从队列中删除，将该节点的左右节点加入队列。循环结束，队列中有2个元素。

（3）从队列中循环取两次元素，每次取出元素，将该元素的左右节点加入队列。等循环结束，记录当前队列长度。由于节点9没有左右节点，节点20有两个子节点。所以该队列长度为2。

（4）循环2次，取出队列中的数据，由于节点15和7都没有子节点，因此循环结束，队列中数据长度为0。

     下面我们看代码实现，然后就很形象了。

总结：

        二叉树的层次遍历，其实也是一种BFS算法（宽度优先搜索），在实际应用中也很常见，需要我们熟练掌握。

       在日常开发中，也许我们大部分时间都是写业务代码，但是对于提高能力，需要掌握、熟悉这些基本功。当你阅读源码的时候，你会发现很多熟悉的身影。

     后续会写几篇文章，带你见识一下一些框架底层的一些数据结构和算法。

最后放一个二叉树层次遍历的算法模版。

类似的，下面这道题可以练手。