Binary Tree Level Order Traversal II

This approach uses a recursive Depth-First Search (DFS) to traverse the tree. It keeps track of the level of each node to group them correctly. The levels are gathered in a top-down order, and the final list of levels is reversed to achieve the required bottom-up order.

• Initialize an empty list of lists, result.
• If the root is null, return the empty result.
• Create a recursive helper function, dfs(node, level, result).
• Call the helper function with the root, level 0, and the result list.
• Inside the helper function:
  • Base case: if the node is null, return.
  • If level is equal to result.size(), it's the first time we're visiting this level. Add a new empty list to result.
  • Add the node's value to the list at index level: result.get(level).add(node.val).
  • Recursively call for the left child: dfs(node.left, level + 1, result).
  • Recursively call for the right child: dfs(node.right, level + 1, result).
• After the initial DFS call returns, the result list contains the levels in top-down order.
• Reverse the result list using Collections.reverse().
• Return the reversed list.

We can perform a pre-order traversal on the tree while keeping track of the current level. We use a list of lists, result, to store the nodes for each level. The level variable acts as an index into this result list. When we visit a node at a level for the first time, we add a new list to result. Then, we add the node's value to the list corresponding to its level. After the traversal is complete, result will hold the levels from top to bottom. The final step is to reverse this result list to get the bottom-up order.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, 0, result);
        Collections.reverse(result);
        return result;
    }

    private void dfs(TreeNode node, int level, List<List<Integer>> result) {
        if (node == null) {
            return;
        }
        // If we are visiting a new level, add a new list for it.
        if (level >= result.size()) {
            result.add(new ArrayList<>());
        }
        // Add the node's value to the list for its level.
        result.get(level).add(node.val);
        
        // Recurse for children.
        dfs(node.left, level + 1, result);
        dfs(node.right, level + 1, result);
    }
}