蓝桥杯--bfs专题第二个题目（leetcode103二叉树）
文章目录
- 1.题目概述
- 2.思路分析
- 3.代码分析
1.题目概述
这个题目是关于二叉树的锯齿形的遍历：这个锯齿形是什么意思呢？简单的通俗的解释，就是S型的，例如下面的这个示例里面的二叉树：
第一行从左到右：但是只有3；
第二行从右向左：20,9
第三行从左向右：16,7
最后返回的在这个结果就是我们的读取的顺序，其中每一行的结果放到一个数组里面就可以了；
2.思路分析
这个实际上就是我们的二叉树的层序遍历的方法，也就是广度优先遍历，这一层遍历结束之后，再去遍历接下来的一层，以此类推；
但是需要注意的就是我们的这个遍历和传统的方式略有不同，我们的这个遍历需要按照S型的方式去进行，因此这个地方我们需要添加一个标注位，奇数的时候正常的进行遍历（就是从左向右的顺序）；
但是偶数行的时候，需要让这个正常遍历的结果进行逆序，满足这个题目的相关要求；
3.代码分析
- 创建列表，对于特殊的情况（没有节点）进行判断，空的话直接返回这个ret即可；
- 创建队列，因为虽然这个题目是二叉树，我们的这个数据结构是队列，先进先出，之前的那个题目，我们介绍了这个队列的一个基本的使用流程；
- 和之前的那个流程不一样的就是，我们的这个题目需要进行标志位的设置，其他的没什么区别；
- 创建队列，把我们的这个节点添加到队列里面去；
- level就是用来记录，判断我们的这个是偶数层还是奇数层的标志；
- 首先还是按照这个队列的整体思路，使用sz判断什么时候这一层遍历结束（我们需要知道这个节点位于那一层上面，不然没法知道这个结果里面谁和谁是一组的，这个很重要，也是我们这个专题里面的第一个题目的核心方法，不理解的去上面一个题目回顾一下）；
- 每一层的这个数据我们都放到这个temp数组里面去，最后把这个temp添加到我们的返回值ret里面去；
- 我们的这个每一层结束的时候都需要对于level数值进行判断，而且之后要更新，如果是偶数，需要进行这个倒序的处理，满足题目要求；
