# LeetCode Binary Tree Zigzag Level Order Traversal

LeetCode Binary Tree Zigzag Level Order Traversal

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).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its zigzag level order traversal as:

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

talk is cheap, show you the code!

```class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root)return ans;
bool left2right = true;
stack<TreeNode*> stk;
stk.push(root);
while(!stk.empty()) {
stack<TreeNode*> stk2;
vector<int> cand;
size_t n = stk.size();
for (size_t i = 0; i < n; ++i) {
TreeNode* top = stk.top();
stk.pop();
if (!top)continue;
cand.push_back(top->val);
if (left2right) {
stk2.push(top->left);
stk2.push(top->right);
}
else {
stk2.push(top->right);
stk2.push(top->left);
}
}
left2right = !left2right;
if (!cand.empty()) ans.push_back(cand);
stk = stk2;
}
return ans;
}
};
```