*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 :**

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (root == null) { return result; } Stack<TreeNode> currLevel = new Stack<TreeNode>(); Stack<TreeNode> nextLevel = new Stack<TreeNode>(); Stack<TreeNode> tmp; currLevel.push(root); boolean normalOrder = true; while (!currLevel.isEmpty()) { ArrayList<Integer> currLevelResult = new ArrayList<Integer>(); 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.