levelOrder.java

/*
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:

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

Algorithm:
1. Basically use a queue, parentNodeCount, and childrenNodeCount.
2. parentNodeCount is to keep track of the number of nodes in the
current level.
3. childrenNodeCount will be passed to parentNodeCount once 
the parentNodeCount is 0. And childrenNodeCount will be increased
when there is a child for the left/right child of the root node.
*/
/**
 * 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>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        if(root == null) return ret;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        
        que.offer(root);
        int parentCount = 1;
        int childrenCount = 0;
        
        while(!que.isEmpty()) {
            TreeNode node = que.poll();
            list.add(node.val);
            parentCount--;
            
            if(node.left != null) {
                childrenCount++;
                que.offer(node.left);
            }
            
            if(node.right != null) {
                childrenCount++;
                que.offer(node.right);
            }
            
            if(parentCount == 0) {
                ret.add(new ArrayList<Integer>(list));
                list.clear();
                parentCount = childrenCount;
                childrenCount = 0;
            }
        }
        return ret;
    }
}