Given Binary Tree [3,9,20,null,null,15,7]
return its zigzag level order traversal as :
Java Solution :
Time Complexity : O(n) , Space Complexity : O(n) + O(n) = O(n)
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.