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:

1
2
3
4
5
6
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

BFS

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
34
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>(); // result list
        List<Integer> sub; // sub list for each level
        if (root == null){return res;}
        
        Queue<TreeNode> level = new LinkedList<>();
        level.add(root);
        
        while (level.size() > 0){
            sub = new ArrayList<>();
            int levelNum = level.size();
            
            for (int i = 0; i < levelNum; i++){
                TreeNode cur = level.poll();
                if (cur.left != null) level.add(cur.left);
                if (cur.right != null) level.add(cur.right);
                sub.add(cur.val);
            }
            // insert at the beginning of the linkedlist
            res.add(0,sub);
        }
        return res;
    }
}

DFS

The attached is my current recursive solution. In each function call, we pass in the current node and its level. If this level does not yet exist in the output container, then we should add a new empty level. Then, we add the current node to the end of the current level, and recursively call the function passing the two children of the current node at the next level. This algorithm is really a DFS, but it saves the level information for each node and produces the same result as BFS would.

from this post

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