题目描述（中等难度）

和 类似，二叉树的层次遍历。只不过这题要求，第 1 层从左到右，第 2 层从右到左，第 3 层从左到右，第 4 层从右到左，交替进行。

思路分析

大家可以先做下 102 题 吧，直接在 102 题的基础上进行修改即可。从左到右和从右到左交替，所以我们只需要判断当前的 ，层数从 0 开始的话，偶数就把元素添加到当前层的末尾，奇数的话，每次把新元素添加到头部，这样就实现了从右到左的遍历。

解法一 DFS

判断 level 是偶数还是奇数即可。

解法二 BFS 队列

如果是顺序刷题，前边的 ， 98 题，，都用到了 BFS ，应该很熟悉了。

之前我们用一个 while 循环，不停的从队列中拿一个节点，并且在循环中将当前取出来的节点的左孩子和右孩子也加入到队列中。

相比于这道题，我们要解决的问题是，怎么知道当前节点的 。

下边的代码实现后一种，并且对 level 进行判断。

第二种方案

把 102 题 的解释贴过来。

这道题我们要知道当前应该是从左到右还是从右到左，最直接的方案当然是增加一个 level 变量，和上边的解法一样，来判断 是奇数还是偶数即可。

除了增加 level 变量外，我们还可以增加一个 变量来区别当前从左还是从右。此外 的评论里，看到了另外一种想法，不用添加新的变量。我们直接判断当前 ans 的大小，如果大小是 n 代表当前在添加第 n 层。

解法三

我们直接用两个栈（或者队列）轮换着添加元素，一个栈从左到右添加元素，一个栈从右到左添加元素。

总

这道题和 102 题 区别不大，只需要对当前层进行判断即可。解法三用两个栈还是蛮有意思的。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情