Binary Tree Level Order Traversal

Problem:

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]
]

Analysis:
Method 1:
Use two queues. One to record the current level, the other keeps record of the next level. Iterate the current level add the children of each nodes in current level to the next level queue. After the current level queue becomes empty, assign the next level to current level.

Method 2:
Use one queue. Use two counters, one counts the current level number of nodes the other counts the next level number of nodes. Each time remove from the linked list, current level number of nodes decrease and add next level number of nodes accordingly.  When current level counter reaches 0, add current level to the final ArrayList. Then next level counter becomes current level counter. Have to note that the ArrayList is the reference type in Java, if clear the ArraryList<Integer> after adding it to the ArraryList<ArraryList<Integer>> then reuse it, it would clear what's inside the ArraryList<ArraryList<Integer>>. So I created another instance every time current level nodes reaches 0.

Solution:
1. Two Queues

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      if(root==null)  
14:        return alResult;  
15:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
16:      currLevel.add(root);  
17:      while(!currLevel.isEmpty())  
18:      {  
19:        ArrayList<Integer> alLevel=new ArrayList<Integer>();  
20:        LinkedList<TreeNode> nextLevel=new LinkedList<TreeNode>();  
21:        while(!currLevel.isEmpty())  
22:        {  
23:          TreeNode currNode=currLevel.remove();  
24:          alLevel.add(currNode.val);  
25:          if(currNode.left!=null) nextLevel.add(currNode.left);  
26:          if(currNode.right!=null) nextLevel.add(currNode.right);  
27:        }  
28:        currLevel=nextLevel;  
29:        alResult.add(alLevel);  
30:      }  
31:      return alResult;  
32:    }  
33:  }  

2. One queue

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      ArrayList<Integer> alLevel=new ArrayList<Integer>();  
14:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
15:      if(root==null)  
16:        return alResult;  
17:      int curr=1;  
18:      int next=0;  
19:      currLevel.add(root);  
20:      while(!currLevel.isEmpty())  
21:      {  
22:        TreeNode currNode=currLevel.remove();  
23:        curr--;  
24:        alLevel.add(currNode.val);  
25:        if(currNode.left!=null)   
26:        {  
27:          currLevel.add(currNode.left);  
28:          next++;  
29:        }  
30:        if(currNode.right!=null)   
31:        {  
32:          currLevel.add(currNode.right);  
33:          next++;  
34:        }  
35:        if(curr==0)  
36:        {  
37:          curr=next;  
38:          next=0;  
39:          alResult.add(alLevel);  
40:          ArrayList<Integer> alLevelTemp=new ArrayList<Integer>();  
41:          alLevel=alLevelTemp;  
42:        }  
43:      }  
44:      return alResult;  
45:    }  
46:  }