# 103. Binary Tree Zigzag Level Order Traversal

Difficulty: Medium

Frequency: N/A

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,#,#,15,7}`,

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

return its zigzag level order traversal as:

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

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> results;
if (!root) return results;
deque<TreeNode*> deq;
deq.push_front(root);
bool front = true;
while (!deq.empty()) {
int s_size = deq.size();
vector<int> result;
while (s_size) {
if (front) {
TreeNode *cur = deq.front();
deq.pop_front();
result.push_back(cur->val);
if (cur->left) deq.push_back(cur->left);
if (cur->right) deq.push_back(cur->right);
} else {
TreeNode *cur = deq.back();
deq.pop_back();
result.push_back(cur->val);
if (cur->right) deq.push_front(cur->right);
if (cur->left) deq.push_front(cur->left);
}
s_size--;
}
front = !front;
results.push_back(result);
}
return results;
}
};
```

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

## One thought on “103. Binary Tree Zigzag Level Order Traversal”

1. […] Binary Tree Zigzag Level Order Traversal […]

Like