Binary Tree Zigzag Level Order Traversal

Binary Tree Zigzag Level Order Traversal

27%

Accepted

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).

Have you met this question in a real interview? 

Yes

Example

Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        // write your code here
         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if(root == null) return res;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        boolean left = true;
        while(!stack.isEmpty()){
            int size = stack.size();
            ArrayList<Integer> sub = new ArrayList<Integer>();
            Stack<TreeNode> nextStack = new Stack<TreeNode>();
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                sub.add(node.val);
                if(left){
                    if(node.left != null) nextStack.add(node.left);
                    if(node.right != null) nextStack.add(node.right);
                } else {
                    if(node.right != null) nextStack.add(node.right);
                    if(node.left != null) nextStack.add(node.left);
                }
               
            }
            res.add(sub);
            left = !left;
            stack = nextStack;
        }
       
        return res;
    }
}