Leetcode: Binary Tree Zigzag Level Order Traversal

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Understand the Problem:
The problem can be still categorized into BFS problem. The only difference between the regular BFS is it traversed the tree in Zigzag order. 

Recursive Solution:
We can still solve this problem using the regular BFS solution. However, for the even level, we store the nodes at reverse order. At the odd level, we store at the forward order. Then there is no difference between regular BFS and zigZag BFS.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        
        zigzagLevelOrder(root, result, 1);
        
        return result;
    }
    
    private void zigzagLevelOrder(TreeNode root, ArrayList<ArrayList<Integer>> result, int level) {
        if (root == null) return;
        
        if (result.size() < level) {
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            if ((level % 2) == 1) {
                levelList.add(root.val);
            } else {
                levelList.add(0, root.val);
            }
            result.add(levelList);
        } else {
            if ((level % 2) == 1) {
                result.get(level - 1).add(root.val);
            } else {
                result.get(level - 1).add(0, root.val);
            }
        }
        
        zigzagLevelOrder(root.left, result, level + 1);
        zigzagLevelOrder(root.right, result, level + 1);
    }
}

Discussion:
The time complexity for the recursive solution is still O(n^2) since inserting the node at head in the even levels takes O(n) time instead of O(1). 

Iterative Solution:
The iterative solution is very similar to the iterative BFS solution. There are two major difference in order do address this zigzag BFS. One is to save the level information, because we wanna store the node in backward order for even levels. Second, for the even level, we may still insert the nodes at head, as the recursive solution. Or we may employ a stack, and for the dequeued elements from the queue, we push into the stack. At last we pop all elements and append to the array list.

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        int level = 0;
        
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            level++;
            ArrayList<Integer> levelList = new ArrayList<Integer>();
            Stack<Integer> levelStack = new Stack<Integer>();
            
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (level % 2 == 1) {
                    levelList.add(curr.val);
                } else {
                    levelStack.push(curr.val);
                }
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            
            // for even level, dump the elments from the stack to the arraylist
            if (level % 2 == 0) {
                while (!levelStack.isEmpty()) {
                    levelList.add(levelStack.pop());
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}

Discussion:
Since pushing and popping an element from the stack takes O(1) time, the overall time complexity is O(n). For the space complexity, since we employed a queue and stack to store the intermediate result, it takes space of O(n) + O(n) = O(n). So the space complexity is still O(n).

Summary:
So far you should be very familiar with all DFS and BFS traversal problems. The recursive solutions are straight-forward, but tricky to understand every detail. Be familiar with the iterative solution, and how queue, stack and pointers are used.

Update on 9/30/14:

/**
 * Definition for binary tree
 * public 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;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelList = new ArrayList<Integer>();
            if (result.size() % 2 == 0) {
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    levelList.add(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
            } else {
                Stack<Integer> stack = new Stack<Integer>();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    stack.push(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
                
                while(!stack.isEmpty()) {
                    levelList.add(stack.pop());
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}