Binary Tree Level Order Traversal II

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     int height;
12     TreeNode root;
13     
14     public List<List<Integer>> levelOrderBottom(TreeNode root) {
15         this.height = getDepth(root);//获取树的高度
16         this.root = root;
17         
18         List<List<Integer>> list = new ArrayList<List<Integer>>();
19         for(int i = 0; i < height; i++){
20             List<Integer> element = new ArrayList<Integer>();
21             list.add(element);
22         }//this.height没有错
23         preOrder(root, list);
24         
25         return list;
26     }
27     
28     /**
29      * node在tree中高度
30      * @param root
31      * @param node
32      * @return
33      */
34     public int getDepth(TreeNode root, TreeNode node){
35         if(null == root)
36             return -Integer.MAX_VALUE;
37         if(node == root)
38             return 1;
39         else{
40             int maxl = getDepth(root.left, node);
41             int maxr = getDepth(root.right, node);
42             if(maxl > maxr)
43                 return maxl + 1;
44             else
45                 return maxr + 1;
46         }
47     }
48     /**
49      * 获取树的高度
50      * @param root
51      * @return
52      */
53     public int getDepth(TreeNode root){
54         if(null == root){
55             return 0;
56         }else{
57             int maxl = getDepth(root.left);
58             int maxr = getDepth(root.right);
59             return maxl>maxr ? (maxl + 1):(maxr + 1);
60         }
61     }
62     /**
63      * 前序遍历树
64      * @param root
65      */
66     public void preOrder(TreeNode root, List<List<Integer>> list){
67         if(null != root){
68             int height = getDepth(this.root, root);
69             List<Integer> element = list.get(this.height - height);
70             element.add(root.val);
71             preOrder(root.left, list);
72             preOrder(root.right, list);
73         }
74     }
75 }