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]
/ \
9 20
/ \
15 7
return its zigzag level order traversal as :
[3],
[20,9],
[15,7]
]
Java Solution :
Related Articles
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public ListListInteger>> zigzagLevelOrder(TreeNode root) {
ListListInteger>> result = new ArrayListListInteger>>();
if (root == null) {
return result;
}
StackTreeNode> currLevel = new StackTreeNode>();
StackTreeNode> nextLevel = new StackTreeNode>();
StackTreeNode> tmp;
currLevel.push(root);
boolean normalOrder = true;
while (!currLevel.isEmpty()) {
ArrayListInteger> currLevelResult = new ArrayListInteger>();
while (!currLevel.isEmpty()) {
TreeNode node = currLevel.pop();
currLevelResult.add(node.val);
if (normalOrder) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
} else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
}
result.add(currLevelResult);
tmp = currLevel;
currLevel = nextLevel;
nextLevel = tmp;
normalOrder = !normalOrder;
}
return result;
}
}
Time Complexity : O(n) , Space Complexity : O(n) + O(n) = O(n)
Explanation
The problem can be solved easily using two stacks. Let us say the two stacks are currLevel and nextLevel. We would also need a variable normalOrder to keep track of the current level order (whether it is left to right or right to left). We pop from the currLevel stack and add it to the ArrayList currLevelResult. Whenever the current level order is from left to right, push the nodes left child, then its right child to stack nextLevel.Since a stack is a Last In First Out(LIFO) structure, next time when nodes are popped off nextLevel, it will be in the reverse order. On the other hand, when the current level is from right to left, we would push the nodes right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (i.e when currLevel is empty). Please mention in the comments if you have any other optimized solution.
