# 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;
}
};