Sum Root to Leaf Numbers

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:

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int sumNumbers(TreeNode root) {6        List<String> allPaths = new ArrayList<>();7        findPaths(root, "", allPaths);8        9        int totalSum = 0;10        for (String path : allPaths) {11            totalSum += Integer.parseInt(path);12        }13        return totalSum;14    }15    16    private void findPaths(TreeNode node, String currentPath, List<String> allPaths) {17        if (node == null) {18            return;19        }20        21        currentPath += node.val;22        23        if (node.left == null && node.right == null) {24            allPaths.add(currentPath);25            return;26        }27        28        findPaths(node.left, currentPath, allPaths);29        findPaths(node.right, currentPath, allPaths);30    }31}

1. Define a recursive helper function, dfs(node, currentSum), which returns the sum of numbers for the subtree rooted at node.
2. The currentSum parameter holds the numerical value of the path from the root to the parent of node.
3. Base Case: If node is null, it contributes nothing to the sum, so return 0.
4. Update the sum for the current path: currentSum = currentSum * 10 + node.val.
5. Leaf Node Check: If the current node is a leaf (both children are null), it signifies the end of a path. Return the currentSum.
6. Recursive Step: If it's not a leaf, recursively call dfs for the left and right children with the updated currentSum. Return the sum of the results from these two calls: dfs(node.left, currentSum) + dfs(node.right, currentSum).
7. The main function initiates the process by calling dfs(root, 0).

This approach uses a pre-order traversal pattern. We maintain the numerical value of the path from the root to the current node's parent. As we descend to a child node, we update this value.

The formula to update the number at each step is newNumber = currentNumber * 10 + node.val. For example, if we are at node 9 and the path from the root was 4, the currentNumber passed to 9 would be 4. The new number becomes 4 * 10 + 9 = 49.

When we reach a leaf node, the number formed along that path is complete. We return this number. For non-leaf nodes, we recursively call the function for the left and right children and sum their results. This effectively sums up all the numbers from all leaf nodes below.

Here is the implementation:

1class Solution {2    public int sumNumbers(TreeNode root) {3        return dfs(root, 0);4    }5 6    private int dfs(TreeNode node, int currentSum) {7        if (node == null) {8            return 0;9        }10 11        currentSum = currentSum * 10 + node.val;12 13        if (node.left == null && node.right == null) {14            return currentSum;15        }16 17        int leftSum = dfs(node.left, currentSum);18        int rightSum = dfs(node.right, currentSum);19 20        return leftSum + rightSum;21    }22}

1. If the root is null, return 0.
2. Initialize totalSum = 0.
3. Create a stack to store pairs of (TreeNode, currentNumber).
4. Push the initial pair (root, 0) onto the stack.
5. Loop while the stack is not empty:
   • Pop a pair (node, number) from the stack.
   • Calculate the new number for the path to this node: newNumber = number * 10 + node.val.
   • If node is a leaf, add newNumber to totalSum.
   • If node has a right child, push (node.right, newNumber) to the stack.
   • If node has a left child, push (node.left, newNumber) to the stack.
6. Return totalSum.

Instead of relying on the call stack for recursion, we use our own stack. The stack will store pairs of (TreeNode, currentNumber).

We start by pushing the root node and an initial number 0 onto the stack. The main loop continues as long as the stack is not empty. In each iteration, we pop a node and its corresponding path number. We calculate the new number for the path ending at this node. If the node is a leaf, we add this number to our total sum. Otherwise, we push its children (if they exist) onto the stack, along with the new path number. To maintain the pre-order traversal logic (process node, then left, then right), we push the right child onto the stack before the left child.

Here is the implementation:

1import java.util.Stack;2 3// Helper class to store a node and the sum up to it.4class Pair {5    TreeNode node;6    int val;7    Pair(TreeNode node, int val) {8        this.node = node;9        this.val = val;10    }11}12 13class Solution {14    public int sumNumbers(TreeNode root) {15        if (root == null) return 0;16        17        int totalSum = 0;18        Stack<Pair> stack = new Stack<>();19        stack.push(new Pair(root, 0));20        21        while (!stack.isEmpty()) {22            Pair current = stack.pop();23            TreeNode node = current.node;24            int currentSum = current.val;25            26            currentSum = currentSum * 10 + node.val;27            28            if (node.left == null && node.right == null) {29                totalSum += currentSum;30            }31            32            if (node.right != null) {33                stack.push(new Pair(node.right, currentSum));34            }35            if (node.left != null) {36                stack.push(new Pair(node.left, currentSum));37            }38        }39        return totalSum;40    }41}