/**

 * public class TreeNode {

 *   public int key;

 *   public TreeNode left;

 *   public TreeNode right;

 *   public TreeNode(int key) {

 *     this.key = key;

 *   }

 * }

 */

public class Solution {

  public List<List<Integer>> layerByLayer(TreeNode root) {

    // Write your solution here

    // use BFS to solve this, thus, we use queue to maintain the nodes that we have seen but haven't deal with,

    // and for each layer, we maintain a List to store all keys in this layer

    // the tree can be null, then we return a List contains nothing

    // the number of the elements in a single layer is less than Integer.MAX_VALUE

    List<List<Integer>> res = new ArrayList<>();

    if(root==null){

      return res;

    }

    Queue<TreeNode> q = new LinkedList<>();

    q.offer(root);

    while(q.size()>0){

      int size = q.size();

      List<Integer> layer = new ArrayList<>();

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

        TreeNode cur = q.poll();

        if(cur!=null){

          layer.add(cur.key);

        }

        if(cur.left!=null){

          q.offer(cur.left);

        }

        if(cur.right!=null){

          q.offer(cur.right);

        }

      }

      res.add(layer);

    }

    return res;

  }

}