[LeetCode] Binary Tree Level Order Traversal

Problem:

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

Solultion:O(n)

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

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

      doLevel(list,0,root);

      return list;

   }

   public void doLevel(ArrayList<ArrayList<Integer>> list, int height,TreeNode root){
      if(root == null)
         return;

      ArrayList<Integer> curlist = null;
      if( list.size() == height){
         curlist= new ArrayList<Integer>();
  list.add(curlist);
      }else{
  curlist = list.get(height);
      }

      curlist.add(root.val);
      doLevel(list,height+1,root.left);
      doLevel(list,height+1,root.right);
   }
}