這道題A的略煩

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
      

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

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 }      

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 
12     public List<List<Integer>> levelOrderBottom(TreeNode root) {
13         List<List<Integer>> container = new ArrayList<List<Integer>>();
14         if(null == root){
15             return container;
16         }
17         //List<TreeNode> theSameLevel = new ArrayList<TreeNode>();//存放同一層節點
18         Queue<TreeNode> theSameLevel = new LinkedList<TreeNode>();
19         theSameLevel.add(root);
20         while(!theSameLevel.isEmpty()){//theSameLevel不為空
21             List<Integer> oneLevel = new ArrayList<Integer>();
22             Queue<TreeNode> temp = new LinkedList<TreeNode>();//暫存同一層的結點
23             while(!theSameLevel.isEmpty()){
24                 TreeNode cur = theSameLevel.remove();
25                 oneLevel.add(cur.val);
26                 if(null != cur.left) 
27                     temp.add(cur.left);
28                 if(null != cur.right)
29                     temp.add(cur.right);
30             }
31             theSameLevel = temp;
32             container.add(0, oneLevel);
33         }
34         
35         return container;
36         
37     }
38     
39    
40 }