Binary Tree Zigzag Level Order Traversal in Java - LeetCode

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]

    3
   /  \
 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.



About The Author

Subham Mittal has worked in Oracle for 3 years .
For more java articles ,Click here to Subscribe JavaHungry