Sum Root to Leaf Numbers

This approach first generates all root-to-leaf paths, stores them, and then iterates through these paths to calculate the corresponding numbers and their sum. It's straightforward but inefficient due to high space usage.

1. Initialize an empty list, allPaths, to store string representations of the numbers for each root-to-leaf path.
2. Define a recursive helper function findPaths(node, currentPathString, allPaths).
3. In the helper function, if the current node is null, return.
4. Append the current node's value to currentPathString.
5. If the current node is a leaf (both left and right children are null), add the currentPathString to the allPaths list.
6. Recursively call the helper function for the left and right children.
7. After the initial call to findPaths on the root completes, iterate through allPaths.
8. For each string in allPaths, convert it to an integer and add it to a totalSum.
9. Return totalSum.

The core idea is to separate the problem into two distinct steps: path finding and summation.

1. Path Finding: A Depth-First Search (DFS) traversal is used to find all paths from the root to every leaf node. We use a helper function that maintains the current path from the root. When a leaf is encountered, the current path is complete and is added to a list of all paths.

2. Summation: After the traversal is complete, we have a list of all paths (where each path is a list of digits). We iterate through this list. For each path, we convert the sequence of digits into an integer. For example, the path [4, 9, 5] is converted to the number 495. These numbers are then added to a running total.

Here is a code snippet illustrating this approach:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int sumNumbers(TreeNode root) {
        List<String> allPaths = new ArrayList<>();
        findPaths(root, "", allPaths);
        
        int totalSum = 0;
        for (String path : allPaths) {
            totalSum += Integer.parseInt(path);
        }
        return totalSum;
    }
    
    private void findPaths(TreeNode node, String currentPath, List<String> allPaths) {
        if (node == null) {
            return;
        }
        
        currentPath += node.val;
        
        if (node.left == null && node.right == null) {
            allPaths.add(currentPath);
            return;
        }
        
        findPaths(node.left, currentPath, allPaths);
        findPaths(node.right, currentPath, allPaths);
    }
}