Problem #129: Sum Root to Leaf Numbers

Intuition & Strategy Breakdown

Perform DFS traversal maintaining current path number (curr_val * 10 + node.val). At leaf nodes, add current path value to total sum.

Python Solution

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_sum):
            if not node:
                return 0
            
            current_sum = current_sum * 10 + node.val
            
            # If it's a leaf node, return the current path sum
            if not node.left and not node.right:
                return current_sum
            
            # Sum up results from left and right subtrees
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
            
        return dfs(root, 0)

Java Solution

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int currentSum) {
        if (node == null) return 0;
        
        currentSum = currentSum * 10 + node.val;
        
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
}