102. Binary Tree Level Order Traversal Leetcode Java

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

Solution:

Basic Tree traversal technique, BFS. 

Use two counters to determine if current level is finished. Increment curL when offer the treenode into the queue, decrement lastL when process/poll the TreeNode. When lastL hit 0, which means all the nodes in this level has been processed, and all of their children have been offered into the queue and the curL is updated with the numbers of next level's nodes.

 public List<List<Integer>> levelOrder(TreeNode root) {  
    List<List<Integer>> res=new ArrayList<List<Integer>>();  
    if(root==null) return res;  
    List<Integer> levels=new ArrayList<Integer>();  
    LinkedList<TreeNode> q=new LinkedList<TreeNode>();  
    q.offer(root);  
    int curL=0;  
    int lastL=1;  
    while(!q.isEmpty()){  
      TreeNode cur=q.poll();  
      levels.add(cur.val);  
      lastL--;  
      if(cur.left!=null) {  
        q.offer(cur.left);  
        curL++;  
      }  
      if(cur.right!=null) {  
        q.offer(cur.right);  
        curL++;  
      }  
      if(lastL==0){  
        res.add(levels);  
        levels=new ArrayList<Integer>();  
        lastL=curL;  
        curL=0;  
      }  
    }  
    return res;  
   }