Why it works
- Appending a digit means number × 10 + val: the digits already there move one place left. So each node gets exactly the number spelled by the path above it, its own digit included.
- A number is complete only at a leaf, so only a leaf returns its number. An inner node such as 5 returns just what its children return, and 25 never gets into the sum.
- Each call returns the sum of the numbers in its subtree, so the root returns the sum of them all.
Complexity
Time O(n): each node is visited once. Memory O(h), where h is the height of the tree: the call stack holds one path.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗