二叉树的锯齿形层序遍历（ LeetCode 103 ）
一、题目描述
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
二、题目解析
该问题需要用到队列，与之前的二叉树的层次遍历类似，不同点在于在偶数层需要翻转一下。
- 建立一个 queue
- 先把根节点放进去，这时候找根节点的左右两个子节点
- 去掉根节点，此时 queue 里的元素就是下一层的所有节点
- 循环遍历，将结果存到一个一维向量里
- 遍历完之后再把这个一维向量存到二维向量里
- 如果该层为偶数层，则 reverse 翻转一下
- 以此类推，可以完成层序遍历
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
// 设置 res 用来保存输出结果
List<List<Integer>> res = new LinkedList<List<Integer>>();
// 边界情况处理
if(root == null) return res;
// 设置一个队列，用来存储二叉树中的元素
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
// 队列添加二叉树的根节点
nodeQueue.add(root);
// 是否从左至右标志位
boolean isOrderLeft = true;
// 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while (!nodeQueue.isEmpty()) {
// 用来记录 queue 的长度，即每层节点的个数
int size = nodeQueue.size();
// 用来保存每一层节点，保存成功后添加到 res 中
// 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
// 用双端队列是方便调换方向存储不同层的元素
Deque<Integer> levelList = new LinkedList<Integer>();
// 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
// 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
for (int i = 0; i < size; ++i) {
// 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
TreeNode curNode = nodeQueue.poll();
// 先从左往右存储，每次存储在 levelList 的队尾，即 addLast
if (isOrderLeft) {
levelList.addLast(curNode.val);
// 再从右往左存储，每次存储在 levelList 的队头，即 addFirst
} else {
levelList.addFirst(curNode.val);
}
// 将下一层节点值进入队列，如果有，按照从左到右的顺序
// 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
if (curNode.left != null) {
nodeQueue.add(curNode.left);
}
// 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中
if (curNode.right != null) {
nodeQueue.add(curNode.right);
}
}
// 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
res.add(new LinkedList<Integer>(levelList));
// 【从左到右】和【从右到左】的顺序来回交替
isOrderLeft = !isOrderLeft;
}
// 返回 res
return res;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
// 设置 res 用来保存输出结果
vector<vector<int>> res;
// 边界情况处理
if(root == NULL) return res;
// 设置一个队列，用来存储二叉树中的元素
queue<TreeNode*> nodeQueue;
// 队列添加二叉树的根节点
nodeQueue.push(root);
// 是否从左至右标志位
bool isOrderLeft = true;
// 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while (!nodeQueue.empty()) {
// 用来记录 queue 的长度，即每层节点的个数
int size = nodeQueue.size();
// 用来保存每一层节点，保存成功后添加到 res 中
// 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
// 用双端队列是方便调换方向存储不同层的元素
deque<int> levelList;
// 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
// 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
for (int i = 0; i < size; ++i) {
// 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
TreeNode* curNode = nodeQueue.front();
nodeQueue.pop();
// 先从左往右存储，每次存储在 levelList 的队尾，即 addLast
if (isOrderLeft) {
levelList.push_back(curNode->val);
// 再从右往左存储，每次存储在 levelList 的队头，即 addFirst
} else {
levelList.push_front(curNode->val);
}
// 将下一层节点值进入队列，如果有，按照从左到右的顺序
// 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
if (curNode->left != NULL) {
nodeQueue.push(curNode->left);
}
// 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中
if (curNode->right != NULL) {
nodeQueue.push(curNode->right);
}
}
vector<int>v;
while(!levelList.empty()){
int element = levelList.front();
levelList.pop_front();
v.push_back(element);
}
// 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
res.push_back(v);
// 【从左到右】和【从右到左】的顺序来回交替
isOrderLeft = !isOrderLeft;
}
// 返回 res
return res;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的锯齿形层序遍历（ LeetCode 103 ）:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
# 设置 res 用来保存输出结果
res = [ ]
# 边界情况处理
if not root :
return res
# 设置一个队列，用来存储二叉树中的元素
nodeQueue = deque()
# 队列添加二叉树的根节点
nodeQueue.append(root)
# 是否从左至右标志位
isOrderLeft = True
# 遍历队列，直到队列为空，说明访问了二叉树中所有的节点
while nodeQueue :
# 用来记录 queue 的长度，即每层节点的个数
size = len(nodeQueue)
# 用来保存每一层节点，保存成功后添加到 res 中
# 由于需要既可以在队头添加元素、有需要可以在队尾添加元素，因此使用双端队列
# 用双端队列是方便调换方向存储不同层的元素
levelList = collections.deque([])
# 使用 for 循环，将 nodeQueue 中的元素添加的 levelList 中
# 按标志位存入双端队列，再按固定顺序读取下一层节点值进队列
for _ in range(size) :
# 从 queue 中取出一个节点，此时，nodeQueue 已经抛出了这个节点
curNode = nodeQueue.popleft()
# 先从左往右存储，每次存储在 levelList 的队尾，即 appendLast
if isOrderLeft :
levelList.append(curNode.val)
# 再从右往左存储，每次存储在 levelList 的队头，即 appendFirst
else :
levelList.appendleft(curNode.val)
# 将下一层节点值进入队列，如果有，按照从左到右的顺序
# 判断当前节点的左子节点是否有值，如果有，则添加到 nodeQueue 中
if curNode.left :
nodeQueue.append(curNode.left)
# 判断当前节点的右子节点是否有值，如果有，则添加到 nodeQueue 中
if curNode.right :
nodeQueue.append(curNode.right)
# 把存放了每一层元素的数组 levelList 添加到 res 中，注意格式转换，需要转换为数组的形式
res.append(list(levelList))
# 【从左到右】和【从右到左】的顺序来回交替
isOrderLeft = not isOrderLeft
# 返回 res
return res
