蓝桥杯---bfs第二题（二叉树遍历）

1.题目概述

这个题目是关于二叉树的锯齿形的遍历：这个锯齿形是什么意思呢？简单的通俗的解释，就是S型的，例如下面的这个示例里面的二叉树：

第一行从左到右：但是只有3；

第二行从右向左：20,9

第三行从左向右：16,7

最后返回的在这个结果就是我们的读取的顺序，其中每一行的结果放到一个数组里面就可以了；

fig:

2.思路分析

这个实际上就是我们的二叉树的层序遍历的方法，也就是广度优先遍历，这一层遍历结束之后，再去遍历接下来的一层，以此类推；

但是需要注意的就是我们的这个遍历和传统的方式略有不同，我们的这个遍历需要按照S型的方式去进行，因此这个地方我们需要添加一个标注位，奇数的时候正常的进行遍历（就是从左向右的顺序）；

但是偶数行的时候，需要让这个正常遍历的结果进行逆序，满足这个题目的相关要求；

fig:

3.代码分析

1. 创建列表，对于特殊的情况（没有节点）进行判断，空的话直接返回这个ret即可；
2. 创建队列，因为虽然这个题目是二叉树，我们的这个数据结构是队列，先进先出，之前的那个题目，我们介绍了这个队列的一个基本的使用流程；
3. 和之前的那个流程不一样的就是，我们的这个题目需要进行标志位的设置，其他的没什么区别；
4. 创建队列，把我们的这个节点添加到队列里面去；
5. level就是用来记录，判断我们的这个是偶数层还是奇数层的标志；
6. 首先还是按照这个队列的整体思路，使用sz判断什么时候这一层遍历结束（我们需要知道这个节点位于那一层上面，不然没法知道这个结果里面谁和谁是一组的，这个很重要，也是我们这个专题里面的第一个题目的核心方法，不理解的去上面一个题目回顾一下）；
7. 每一层的这个数据我们都放到这个temp数组里面去，最后把这个temp添加到我们的返回值ret里面去；
8. 我们的这个每一层结束的时候都需要对于level数值进行判断，而且之后要更新，如果是偶数，需要进行这个倒序的处理，满足题目要求；

fig: