## [Leetcode]103. Binary Tree Zigzag Level Order Traversal(C++)

### 题目描述

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

### 例子

Input: `[3,9,20,null,null,15,7]` Output:

``````[
[3],
[20,9],
[15,7]
]
``````

### 解题思路

• 从 0 层开始，当前层为偶数时，从左往右输出
• 奇数时从右往左输出

• 当前在偶数层时，节点从左往右输出，此时对每一个节点，先压左节点再压右节点，保持相对顺序
• 在奇数层时则相反

``````#include <vector>
#include <stack>

class Solution {
public:
std::vector<std::vector<int>> zigzagLevelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (root == nullptr) return result;
std::stack<TreeNode*> curr_level_nodes;
curr_level_nodes.push(root);
int curr_level = 0;
while (!curr_level_nodes.empty()) {
std::vector<int> curr_level_vals;
std::stack<TreeNode*> next_level_nodes;
while (!curr_level_nodes.empty()) {
TreeNode* node = curr_level_nodes.top();
curr_level_nodes.pop();
if (curr_level % 2 == 0) {
// if even level, push children from left to right
if (node->left) next_level_nodes.push(node->left);
if (node->right) next_level_nodes.push(node->right);
}
else {
// if odd level, push children from right to left
if (node->right) next_level_nodes.push(node->right);
if (node->left) next_level_nodes.push(node->left);
}
curr_level_vals.push_back(node->val);
}
result.push_back(curr_level_vals);
++curr_level;
curr_level_nodes = next_level_nodes;
}

return result;
}
};
``````
• 时间复杂度: O(n)
• 空间复杂度: O(w)

GitHub 代码同步地址： 103.BinaryTreeZigzagLevelOrderTraversal.cpp

Built with Hugo
Theme Stack designed by Jimmy