129. Sum Root to Leaf Numbers
Every node of a binary tree holds a single digit, 0 through 9. Reading the digits along a path from the root down to a leaf spells out a number: the path 4 → 9 → 5 spells 495.
Your function receives the root of such a tree and returns the sum of the numbers spelled by every root-to-leaf path. A leaf is a node with no children; the tree has at least one node, and every answer fits in a 64-bit integer.
For example, a root 1 with children 2 and 3 has two paths — 12 and 13 — so the answer is 25.
Example 1:
Input: root = [1, 2, 3]
Output: 25
Explanation: The two root-to-leaf paths are 1→2 and 1→3, spelling 12 and 13. Their sum is 25.
Example 2:
Input: root = [4, 9, 0, 5, 1]
Output: 1026
Explanation: Three paths: 4→9→5 spells 495, 4→9→1 spells 491, and 4→0 spells 40. 495 + 491 + 40 = 1026.
Constraints:
- 1 ≤ number of nodes ≤ 1000
- 0 ≤ node value ≤ 9
- The tree's depth is at most 10, so every path number fits in a 64-bit integer.
Hints:
Carry the number built so far as you descend: entering a node with digit d turns the running value acc into acc · 10 + d.
When you land on a leaf, the running value is a complete path number — add it to the total. Internal nodes contribute nothing by themselves.
One DFS that returns the sum of its left and right subtree results (or the running value at a leaf) solves it in a single pass with no string building.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3]
Expected output: 25