5.6 Binary Tree Level Order Traversal II

5.6.1 Problem Metadata

5.6.2 Description

Return the level order traversal of a binary tree from the bottom level up to the root.

5.6.3 Examples

Input: [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

5.6.4 Constraints

  • 0 <= nodes <= 2000

5.6.5 Solution - Reverse BFS

5.6.5.1 Walkthrough

Perform BFS collecting nodes level by level. Instead of appending to the end, insert each level at the front of a linked list (or append and reverse at the end).

5.6.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

5.6.5.3 Implementation Steps

  1. Run BFS using a queue.
  2. For each level size, dequeue nodes, record values, enqueue children.
  3. Insert level list at the start of the result.

5.6.5.4 Code - Java

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    LinkedList<List<Integer>> result = new LinkedList<>();
    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>(size);

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        result.addFirst(level);
    }

    return result;
}