/**

  * Definition of TreeNode:

  * public class TreeNode {

  *     public int val;

  *     public TreeNode left, right;

  *     public TreeNode(int val) {

  *         this.val = val;

  *         this.left = this.right = null;

  *     }

  * }

  */

 public class Solution {

     /**

      * @param root: The root of binary tree.

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

      */

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

         // write your code here

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

         if (root == null ){

             return result;

         }

         BFS(root,result);

         return result;

     }

     /*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()

         implemented the queue by using linkedList*/

     public void BFS (TreeNode root, ArrayList<ArrayList<Integer>> lists) {

         ArrayList<TreeNode> queue = new ArrayList<TreeNode> ();

         queue.add(root);

         int maxDepth=0;

         while (!queue.isEmpty()) {

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

             int levelSize = queue.size();

             for (int i = 0; i < levelSize; i++) {

                 TreeNode curr = queue.remove(0);

                 list.add(curr.val);

                 if (curr.left != null) {

                     queue.add(curr.left);

                 }

                 if (curr.right != null) {

                     queue.add(curr.right);

                 }

             }

             lists.add(list);

         }

     }

 }