Binary Tree Level Order Traversal II

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

Java语言: 高亮代码由发芽网提供

01 public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
02   ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03   if(root==null)
04     return results;
05 
06   ArrayList<TreeNode> trees=new ArrayList<TreeNode>();
07   ArrayList<Integer> depth=new ArrayList<Integer>();
08 
09   ArrayList<Integer> first=new ArrayList<Integer>();
10   first.add(root.val);
11   results.add(first);
12 
13   trees.add(root);
14   int level=1;
15   depth.add(level);
16 
17   while(!trees.isEmpty())
18   {
19     TreeNode top=trees.remove(0);
20     int curr_level=depth.remove(0);
21     if(top.left!=null)
22     {
23       trees.add(top.left);
24       depth.add(curr_level+1);
25     }
26     if(top.right!=null)
27     {
28       trees.add(top.right);
29       depth.add(curr_level+1);
30     }
31   
32     int size=depth.size();
33   
34     if(size>0 && depth.get(0)==depth.get(size-1)&& depth.get(0)==curr_level+1)
35     {
36     
37       ArrayList<Integer> levelNodes=new ArrayList<Integer>();
38       for(int i=0;i<size;i++)
39       {
40         levelNodes.add(trees.get(i).val);
41       }
42       results.add(0,levelNodes);
43     
44     }
45   
46   }
47 
48   return results;
49 }