Binary Tree Level Order Traversal

Problem description
Level: medium
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

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

return its level order traversal as:

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

Challenge
Using only 1 queue to implement it.

Consideration

There are multiple approaches to solve the problem.
1. two queues ( queue 1 save one level, then find nodes for next level, save in to queue 2, then clean queue 1, find next level nodes save them in queue 1)
2. one queue + dummy number (use # as level break, 3 # 9 20 # 15 7)
3. one queue
4. no queue

Solution 1 (no queue)


    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    	ArrayList<ArrayList<Integer>> lsts = new ArrayList<ArrayList<Integer>>();
    	helper(root, lsts, 1);
    	
    	return lsts;
    }

    public static void helper(TreeNode node, ArrayList<ArrayList<Integer>> lsts, int height) {
    	if(node == null) return;
    	
    	if(lsts.size() < height) {
    		ArrayList<Integer> lst = new ArrayList<Integer>();
    		lst.add(node.val);
    		lsts.add(lst);
    	} else {
    		lsts.get(height - 1).add(node.val);
    	}
    	helper(node.left, lsts, height + 1);
    	helper(node.right, lsts, height + 1);
    }

/**

* @param root: The root of binary tree.

* @return: Level order a list of lists of integer

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {

ArrayList<ArrayList<Integer>> lsts = new ArrayList<ArrayList<Integer>>();

helper(root, lsts, 1);

return lsts;

}

public static void helper(TreeNode node, ArrayList<ArrayList<Integer>> lsts, int height) {

if(node == null) return;

if(lsts.size() < height) {

ArrayList<Integer> lst = new ArrayList<Integer>();

lst.add(node.val);

lsts.add(lst);

} else {

lsts.get(height - 1).add(node.val);

}

helper(node.left, lsts, height + 1);

helper(node.right, lsts, height + 1);

}

Solution 2 – one queue


    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    	ArrayList<ArrayList<Integer>> lsts = new ArrayList<ArrayList<Integer>>();
    	if(root == null) { return lsts; }
    	
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.offer(root);
    	
    	while(!queue.isEmpty()) {
    		ArrayList<Integer> level = new ArrayList<Integer>();
    		int size = queue.size();
    		for(int i = 0; i < size; i++) {  // execute how many times
    			TreeNode node = queue.poll();
    			level.add(node.val);
    			if(node.left != null) { queue.offer(node.left); }
    			if(node.right != null) { queue.offer(node.right); }
    		}
    		lsts.add(level);
    	}
    	
    	return lsts;
    }