Get Keys In Binary Tree Layer By Layer

Get the list of list of keys in a given binary tree layer by layer. Each layer is represented by a list of keys and the keys are traversed from left to right.

Examples

3 8

1 4 11

the result is [ [5], [3, 8], [1, 4, 11] ]

Corner Cases

What if the binary tree is null? Return an empty list of list in this case.

How is the binary tree represented?

We use the level order traversal sequence with a special symbol "#" denoting the null node.

For Example:

The sequence [1, 2, 3, #, #, 4] represents the following binary tree:

2 3

/**
 * 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;
  }
}