Sum Root to Leaf Numbers

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 path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers.

Examples

Example 1:

Input: root = [1, 2, 3]
Output: 25
Explanation: 12 + 13 = 25

    1
   / \
  2   3

Example 2:

Input: root = [4, 9, 0, 5, 1]
Output: 1026
Explanation: 495 + 491 + 40 = 1026

      4
     / \
    9   0
   / \
  5   1

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.

Expected Complexity

• Time: O(n)
• Space: O(h) where h is the height of the tree