Binary Tree Level Order Traversal II

Problem

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],
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

Solution

BFS Solution using Queue

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; 
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int level = queue.size();
            while (level > 0) {
                if (queue.peek().left != null) queue.offer(queue.peek().left);
                if (queue.peek.right != null) queue.offer(queue.peek().right);
                list.add(queue.poll().val);
                level--;
            }
            res.add(0, list);
        }
        return res;
    }
}

DFS Solution using helper() function

public class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        helper(res, root, 0);
        return res;
    }

    private void helper(List<List<Integer>> res, TreeNode node, int level) {
        if (node == null) return;
        if (level >= res.size()) res.add(0, new ArrayList<>());
        helper(res, node.left, level + 1);
        helper(res, node.right, level + 1);
        res.get(res.size() - 1 - level).add(node.val);
    }
}

Analysis

A typical traversal problem of Binary Tree
We need to collect all nodes in the same level

In the BFS solution, we make use of queue.size() to know which level it is
We first call queue.peek() and add the left and right node into queue if they are not null
Then we add the current node's val into the list
After adding a level, we add the list in the first index to our res

In the DFS solution, we first create empty list as long as we reach the new level
We go through all the left and right of current node by recursively calling the helper() method
At the end, we get the correct list from res with index res.size() - 1 (last one) - level

Complexity:

• Time: O(n^2) for both solutions
• Space: O(n) for both solutions