[LeetCode] Binary Tree Level Order Traversal II

Problem:

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

Solution:O(n)

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        doOrder(list,root,0);
        Collections.reverse(list);  
        return list;
    }
    public void doOrder(ArrayList<ArrayList<Integer>> list,TreeNode root, int level){
        if(root == null)
            return;
        int size = list.size();
        if(size == level){
            ArrayList<Integer> curlist = new ArrayList<>();  
            curlist.add(root.val);
            list.add(curlist);
        }else{
           list.get(level).add(root.val);
        }
        doOrder(list, root.left, level+1);  
        doOrder(list, root.right, level+1);
    }
}