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

Example:

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

return its zigzag level order traversal as:

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

### # Solution

Approach 1: DFS.

Approach 2: BFS with queue.

Approach 3: BFS with two stacks.

### # Code (Python)

Approach 1:

``````from collections import deque
class Solution:
def zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
# recursive
result = []
self._traverse(root, 0, result)
return list(map(list, result))

def _traverse(self, node, level, result):
if not node:
return
if len(result) == level:
result.append(deque())
if level % 2 == 0:
result[level].append(node.val)
else:
result[level].appendleft(node.val)
if node.left:
self._traverse(node.left, level + 1, result)
if node.right:
self._traverse(node.right, level + 1, result)
``````

Approach 2:

``````    def zigzagLevelOrder(self, root):
# iterative
if not root:
return []
result = []
level = [root]
reverse = False
while level:
current_level = deque()
next_level = []
for node in level:
if not reverse:
current_level.append(node.val)
else:
current_level.appendleft(node.val)
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
result.append(list(current_level))
level = next_level
reverse = (not reverse)
return result
``````

### # Code (C++)

Approach 1:

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
// DFS.
class Solution {
private:
vector<vector<int>> res;
void doZigzagLevelOrder(TreeNode *root, int level) {
if (root == NULL)
return;
if (res.size() < level)
res.push_back(vector<int>());
if (level % 2 != 0)
res[level-1].push_back(root->val);
else
res[level-1].insert(res[level-1].begin(), root->val);
doZigzagLevelOrder(root->left, level + 1);
doZigzagLevelOrder(root->right, level + 1);
}
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
doZigzagLevelOrder(root, 1);
return res;
}
};
``````

Approach 2:

``````// BFS with queue.
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
queue<TreeNode*> q;
if (root)
q.push(root);
bool leftToRight = true;
while (!q.empty())
{
int qSize = q.size();
vector<int> buf;
for (int i = 0; i < qSize; ++i)
{
TreeNode *curr = q.front();
q.pop();
if (leftToRight)
buf.push_back(curr->val);
else
buf.insert(buf.begin(), curr->val);
if (curr->left)
q.push(curr->left);
if (curr->right)
q.push(curr->right);
}
if (buf.size() > 0)
res.push_back(buf);
leftToRight = !leftToRight;
}
return res;
}
};
``````

Approach 3:

``````// BFS with two stacks.
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
stack<TreeNode*> st[2];
int stIdx = 0;
if (root)
st[stIdx].push(root);
while (!st[stIdx].empty())
{
vector<int> buf;
while (!st[stIdx].empty())
{
TreeNode *curr = st[stIdx].top();
st[stIdx].pop();
buf.push_back(curr->val);
if (stIdx == 0)
{
if (curr->left)
st[1].push(curr->left);
if (curr->right)
st[1].push(curr->right);
}
else
{
if (curr->right)
st[0].push(curr->right);
if (curr->left)
st[0].push(curr->left);
}
}
if (buf.size() > 0)
res.push_back(buf);
stIdx = 1 - stIdx;
}
return res;
}
};
``````