Problem
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example
Example 1
Tree Traversal Direction
3 ->
/ \
9 20 <-
/ \
15 7 ->
Input: root = [3,9,20,null,null,15,7]
Output: [
[3],
[20,9],
[15,7]
]
Solution
Method 1 - Using 2 Stacks
We can use 2 stacks. We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level?
If we think logically then we will see that we need stack in place of queue. Now again a single stack won’t serve our purpose here, we need 2 stacks: stack1 for right to left and stack2 for left to right. For identifying, whether we need to put data in stack1 or stack2, we need a flag (left2right) to indicate direction (after a level finishes).
Initially, left2right is true and we push root node in stack1 and that’s our beginning point. Now since after root node, first level fished, we toggle left2right to false. Until stack1 is empty, we pop values from stack1 and push values based on left2right flag. Once stack1 finishes, we toggle left2right again and switch stack’s role. For clarification, when left2right is true, push left node first in stack and then right node. Similarly left2right is false, push right node first in stack and then left node.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
Stack<TreeNode<Integer>> currLevel = new Stack<>();
Stack<TreeNode<Integer>> nextLevel = new Stack<>();
Stack<TreeNode<Integer>> temp;
boolean leftToRight = true;
// push root in stack
currLevel.push(root);
List<Integer> level = new LinkedList<>();
while (!currLevel.empty()) {
TreeNode<Integer> node = currLevel.pop();
level.add(node.val);
if (node != null) {
if (leftToRight) {
//if left to right, start pushing from left
pushToStack(nextLevel, node.left);
pushToStack(nextLevel, node.right);
} else {
//else push the right node first
pushToStack(nextLevel, node.right);
pushToStack(nextLevel, node.left);
}
}
if (currLevel.isEmpty()) {
result.add(level);
level = new LinkedList<Integer>();
leftToRight = !leftToRight;
//swap stacks
temp = currLevel;
currLevel = nextLevel;
nextLevel = temp;
//we can also set currLevel = nextLevel and instantiate nextLevel again
//nextLevel = new Stack<TreeNode>();
}
}
return result;
}
private void pushToStack(Stack<TreeNode<Integer>> stack, TreeNode<Integer> node) {
if (node != null) {
stack.push(node);
}
}
Method 2 - Using Level Order Traversal with Queue and Stack
If we look closely then we can notice that this is basically a level order (or horizontal) traversal where we are changing direction (left or right) at alternate level. This problem in a way is similar to Binary Tree Level Order Traversal - Level by Level.
We can keep a stack to save the nodes in reverse order (right to left) if we are in a even level. At the end of an even level we will print from the stack. On the other hand for odd level we just print as we traverse from left to right. Below is the implementation of this level order traversal using a queue.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
queue.offer(root);
boolean leftToRight = true;
Stack<TreeNode> reverse = new Stack<TreeNode>();
List<Integer> currLevel = new LinkedList<>();
List<List<Integer>> ans = new LinkedList<>();
while (!queue.isEmpty()) {
int sz = queue.size();
currLevel = new LinkedList<>();
ans.add(currLevel);
for (int i = 0; i < sz; i++) {
TreeNode curr = queue.poll();
if (leftToRight) {
currLevel.add(curr.val);
} else {
reverse.push(curr.val);
}
if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
// level has ended
if (i == sz-1) {
if (!leftToRight) {
while(!reverse.isEmpty()) {
currLevel.add(reverse.pop());
}
}
}
}
leftToRight = !leftToRight;
}
return ans;
}
Method 3 - Using 1 Queue and reversing current level alternatively
Idea is to take all nodes at each level and print them forward and reverse order alternatively.
- Create a list
currLevel. - Do the Binary Tree Level Order Traversal - Level by Level.
- For getting all the nodes at each level, before you take out a node from queue, store the size of the queue in a variable, say you call it as
sz. - Now while
sz>0, take out the nodes and add it to the array list and add their children into the queue. - Alternatively take the list in forward and backward order.
- After this while loop put a line break.
Time Complexity : O(N)
Code:
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<>();
if (root == null) {
return ans;
}
Queue<TreeNode> q = new LinkedList<>();
q.add(root);
List<Integer> currLevel = new LinkedList<>();
boolean leftToRight = true;
while (!q.isEmpty()) {
int sz = q.size();
currLevel = new LinkedList<>();
while (sz> 0) {
TreeNode curr = q.poll();
currLevel.add(curr.val);
if (curr.left != null) {
q.offer(curr.left);
}
if (curr.right != null) {
q.offer(curr.right);
}
sz--;
}
if (!leftToRight) {
Collections.reverse(currLevel);
}
leftToRight = !leftToRight;
ans.add(currLevel);
}
return ans;
}
Method 4 - Using Recursion with pre-order traversal
We can also use recursion like below.
public List < List<Integer>> zigzagLevelOrder(TreeNode root) {
List < List<Integer>> ans = new ArrayList<>();
travel(root, ans, 0);
return ans;
}
private void travel(TreeNode curr, List < List<Integer>> ans, int level) {
if (curr == null) {
return;
}
// ans size expands with level
if (ans.size() <= level) {
List<Integer> newLevel = new LinkedList<>();
ans.add(newLevel);
}
List<Integer> currLevel = sol.get(level);
boolean leftToRight = level % 2 == 0;
if (leftToRight) {
currLevel.add(curr.val);
}
else {
currLevel.add(0, curr.val);
}
travel(curr.left, ans, level + 1);
travel(curr.right, ans, level + 1);
}