Sum Root to Leaf Numbers

Intuition

Concatenating digits along a path is just building a base-10 number one digit at a time. Every time we step from a parent to a child we shift the accumulated value left by one digit (multiply by ten) and add the child's digit. When we reach a leaf, the accumulated value is exactly the number that path represents, so it contributes directly to the answer. Passing the running number down as a parameter means each node computes its contribution without any global bookkeeping. Summing the results from the left and right subtrees gives the total for the whole tree.

Algorithm walkthrough

1. 1Define a DFS that receives the current node and the number built so far along the path from the root.
2. 2If the node is null, it contributes nothing, so return 0.
3. 3Update current = current * 10 + node.val to fold this node's digit into the running number.
4. 4If the node is a leaf, return current because the path number is complete.
5. 5Otherwise return the sum of the DFS results for the left and right children.
6. 6Kick off the recursion with current = 0 at the root and return its result.

Implementation

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if not node:
                return 0
            current = current * 10 + node.val
            if not node.left and not node.right:
                return current
            return dfs(node.left, current) + dfs(node.right, current)

        return dfs(root, 0)