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 -> 3
represents 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:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Therefore, sum = 12 + 13 = 25
.
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5
represents the number 495.
The root-to-leaf path 4->9->1
represents the number 491.
The root-to-leaf path 4->0
represents the number 40.
Therefore, sum = 495 + 491 + 40 = 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
.
SOLUTION:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
paths = [(root, root.val)]
i = 0
total = 0
while i < len(paths):
curr, val = paths[i]
if curr:
if not curr.left and not curr.right:
total += val
if curr.left:
paths.append((curr.left, 10 * val + curr.left.val))
if curr.right:
paths.append((curr.right, 10 * val + curr.right.val))
i += 1
return total
Top comments (0)