LintCode Binary Tree Level Order Traversal

 1 /**
 2  * Definition of TreeNode:
 3  * public class TreeNode {
 4  *     public int val;
 5  *     public TreeNode left, right;
 6  *     public TreeNode(int val) {
 7  *         this.val = val;
 8  *         this.left = this.right = null;
 9  *     }
10  * }
11  */
12  
13  
14 public class Solution {
15     /**
16      * @param root: The root of binary tree.
17      * @return: Level order a list of lists of integer
18      */
19     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
20         // write your code here
21         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
22         if (root == null ){
23             return result;
24         }
25         BFS(root,result);
26         return result;
27     }
28     /*At first I was trying to use BFS but I have no idea how to get all nodes in same layer to outputh to one list until I saw some answer from jiuzhang suanfa. It is obviously that the number of nodes is the queue‘s size before offerl()
29         implemented the queue by using linkedList*/
30     public void BFS (TreeNode root, ArrayList<ArrayList<Integer>> lists) {
31         ArrayList<TreeNode> queue = new ArrayList<TreeNode> ();
32         queue.add(root);
33         int maxDepth=0;
34         while (!queue.isEmpty()) {
35             ArrayList<Integer> list = new ArrayList<Integer>();
36             int levelSize = queue.size();
37             for (int i = 0; i < levelSize; i++) {
38                 TreeNode curr = queue.remove(0);
39                 list.add(curr.val);
40                 if (curr.left != null) {
41                     queue.add(curr.left);
42                 }
43                 if (curr.right != null) {
44                     queue.add(curr.right);
45                 }
46             }
47             lists.add(list);
48         }
49     }
50     
51 }