leetcode #107 Binary Tree Level Order Traversal II
z
 2017-12-22 21:10:46  

107. 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,null,null,15,7],

1
2
3
4
5
6
  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

1
2
3
4
5
6
[
  [15,7],
  [9,20],
  [3]
]

树的遍历，深度优先算法

加了一个小trick

在每进入新的一层后，如果当前层大于result中的LinkedList数目，则为result创建一个新的LinkedList，创建的位置不是在最后，而是在最前面创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(root != null)
            levelAdd(result, root, 0);
        return result;
    }
    public void levelAdd(List<List<Integer>> result,TreeNode root, int level){
        if (result.size()<=level)
            result.add(0, new LinkedList<Integer>());
        if(root.left == (null) && root.right == (null)) 
            ;
        else if(root.right == null)  
            levelAdd(result, root.left, level+1);
        else if(root.left ==null)  
            levelAdd(result, root.right, level+1);
        else{
            levelAdd(result, root.left, level+1);
            levelAdd(result, root.right, level+1);
        }
        result.get(result.size()- level-1).add(root.val);
    }
    
}

上面版本有些累赘，可以参考下面的版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
            levelMaker(wrapList, root, 0);
            return wrapList;
        }
        
        public void levelMaker(List<List<Integer>> list, TreeNode root, int level) {
            if(root == null) return;
            if(level >= list.size()) {
                list.add(0, new LinkedList<Integer>());
            }
            levelMaker(list, root.left, level+1);
            levelMaker(list, root.right, level+1);
            list.get(list.size()-level-1).add(root.val);
        }
    }