Sum Root to Leaf Numbers
Medium · tree dfs
You are given the root of a binary tree in which every node holds a single digit from 0 to 9.
Every path that starts at the root and ends at a leaf spells a number: read the digits from the top down, so the path 1 -> 2 -> 3 spells 123. A leaf is a node with no children. Leading zeros are fine, so the path 0 -> 4 -> 2 spells 42.
Return the sum of the numbers spelled by all root-to-leaf paths. The tree has at most 9 levels, so every number has at most 9 digits, and the total is guaranteed to fit in a 32-bit signed integer.
Examples
Example 1
Input: root = [4, 9, 0, 5, 1]
Output: 1026
The paths 4-9-5, 4-9-1 and 4-0 spell 495, 491 and 40, and 495 + 491 + 40 = 1026.
Example 2
Input: root = [2, 3, 5]
Output: 48
The two paths spell 23 and 25.
Example 3
Input: root = [7]
Output: 7
The root is also a leaf, so the only path is the single digit 7.
Constraints
- The number of nodes is in the range [1, 500].
- 0 <= Node.val <= 9
- The tree has at most 9 levels, so no root-to-leaf path has more than 9 nodes.
- The answer fits in a 32-bit signed integer.