二叉树的层序遍历

层序遍历就是从左到右一层一层的遍历二叉树，相当于图论中的广度优先搜索。二叉树的层序遍历需要借助队列这种数据结构，因为队列的特点是先进先出，符合层序遍历的逻辑。

102.二叉树的层序遍历：这道题是后续与二叉树层序遍历相关问题的基石。整个二叉树用一个List集合保存(代码中命名为了result)，而这个集合中保存的是多个子集合，每个子集合表示二叉树中每层的所有元素(代码中命名为了level)。具体实现如下：

queue这个集合用于模拟队列，保存每个处理过的结点。

thisLevel表示当前处理的这层有多少个结点，nextLevel用于判断下一层有多少个结点。

while循环在队列中还有结点没有出队的时候，会继续对其进行处理，直至队列中没有任何结点存在。

for循环用于处理每一层中的所有节点，如果这层有一个结点，则循环一次；若这一层有两个结点，则循环两次；若这一层有四个结点，则循环四次。

这样通过双层嵌套循环，即可完成二叉树的层序遍历。其实如果仅仅按层序顺序输出结点的值，一次循环即可实现。但是如果要让每一层的数据用一个集合保存，则需要嵌套循环才能实现。

107.二叉树的层序遍历Ⅱ：这道题只需要倒置102题最终得到的结果集合即可。

199.二叉树的右视图：这道题只用将层序遍历得到的二叉树中的每个子集合的最后一个元素拿出来，按层次的顺序依次加入到结果集合中即可。

637.二叉树的层平均值：这道题只需要将二叉树每一层的数据求和并求出平均值即可，最终结果中包含的平均值的数量等于二叉树一共有几层。

429.N叉树的层序遍历：这道题还稍微有点难度，具体实现如下：

这里要注意的是，这题卡了很久，问题出在最内层循环的数组下标越界(如果不使用get(0)而是使用get(i)进行队列中元素访问的话，最后一个结点在访问时可能会用get(i)(在这里i=1，但其实这时队列长度仅为1，所以只有一个下标为0的元素可以被访问)。但其实最内层循环处理的每次都是队列的第一个结点，在每次都将下标为0的结点的孩子加入队列之后，即最内层循环执行完毕后，都会将下标为0的结点出队列，这样下次访问的还是下标为0的结点。所以最内层循环始终使用get(0)即可。

515.在每个树行中找最大值：这道题很简单，把保存每一层值的集合进行一次遍历，找到每一层中最大的值加入最终的result集合即可。

116.填充每个结点的下一个右侧结点指针：这道题只需要遍历每一层中的所有结点并对遍历到的结点进行处理即可。若该结点不是其所在层的最后一个结点，则其next指针指向其所在层与之相邻的右侧结点；若该结点是其所在层的最后一个结点，则其next指针的值为null即可。最后将整个二叉树的第一个结点返回即可。

117.填充每个结点的下一个右侧结点指针Ⅱ：这道题的解法同116相同。

104.二叉树的最大深度：这道题就是返回二叉树有多少层。

111.二叉树的最小深度：这道题只需要找到第一个叶子节点，然后直接返回叶子节点所在层数即可。