树的层次遍历总结

最近正巧Leetcode出了每日一题计划，本着蹭点积分的原则，每天都会写几道题，做了一些关于树的层次遍历的题目，都是一样的套路，简单总结一下几道关于层次遍历的题目。

102. 二叉树的层次遍历

这到题是我们做后面层次遍历变形题目的基础，只要掌握了这个，才能做后面的题目。层次遍历也叫BFS，即广度优先遍历，使用队列来实现（也可以使用递归，但这里不会写，因为我觉得大部分层次遍历的题目用迭代的方式比较容易理解）。下面就是层次遍历的模板，需要注意的点都已经用注释标注了。如果实在理解不了的话背下来也是可以的。

103. 二叉树的锯齿形遍历

我们可以发现，返回结果有这样的规律，奇数层从左到右遍历，偶数层从右到左遍历，那这样我们就可以动手在层次遍历的模板上进行更改了。

做法也比较简单，我们只需要一个变量来记录当前遍历到第几层，再根据该层的奇偶性质进行正序或者逆序的添加即可。

107. 二叉树的层次遍历2

这道题和102题没什么不同，只是要求结果是从最低层到最高层逆序输出。我们可以使用102题的代码，最后将集合逆序即可。或者使用103题的技巧，在添加的整个层的时候就进行逆序添加。

116.填充节点的下一个右侧节点指针

从图中我们可以看出，其实相当于将每层的节点组成一个单链表。我们只需要在遍历的时候将该层的节点组合成链表即可

这里当存储每层集合的list为空时，意味着我们遍历的节点是头结点，我们将它记录下来。下次进入该层时，将pre节点的next指针指向正在遍历的节点。最后在每层遍历结束的时候，将pre的next指针指向空即可。

199. 二叉树的右视图

这道题我一开始看到觉得无从下手，后来发现只是层次遍历的换法描述而已。换成这样的描述会更清晰：求每层节点的最右侧节点。其实从右侧能看到的节点就是每层最右侧的节点。这就又回到层次遍历上来，我们只需要找到每层的最后一个节点即可。

513：树左下角的值
给定一个二叉树，在树的最后一行找到最左边的值。

这个题在有了上面的基础下应该就比较简单了，我们可以使用一个变量记录每层的第一个节点，然后不断进行更新就可以了。这里代码就不贴出来了。

515. 求树中每行最大值
您需要在二叉树的每一行中找到最大的值。

这个题也没什么好说的，可以在遍历每层的时候不断更新每层的最大值放入结果，也可以将每层的结果存入集合，最后再做统一处理。

637：二叉树的层平均值
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组

这题与515几乎一样，不多说。与之类似的题还有【1302：层数最深叶子节点的和】等等

总结

二叉树层次遍历的题目比较简单，基本就是套模板，无非就是使用点技巧在遍历的过程中求出结果，或者慢一点求出每层的集合再遍历求最后的结果。总之记住层次遍历的模板就ok拉。