Sum Root to Leaf Numbers
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1
1
/ \
2 3Input
root = [1,2,3]Output
25The root-to-leaf paths represent 12 and 13, so the total sum is 25.
Example 2
4
/ \
9 0
/ \
5 1Input
root = [4,9,0,5,1]Output
1026The root-to-leaf paths represent 495, 491, and 40, so the total sum is 1026.
Constraints
- The number of nodes in the tree is in the range
[1, 1000]. 0 <= Node.val <= 9- The depth of the tree will not exceed
10.