LeetCode Top Interview 150

129. Sum Root to Leaf Numbers

Medium

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 number 123.

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

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        self.sum_total = 0

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        self._recurseSum(root, 0)
        return self.sum_total

    def _recurseSum(self, node: Optional[TreeNode], cur_num: int):
        if node.left is None and node.right is None:
            self.sum_total += 10 * cur_num + node.val
        else:
            if node.left is not None:
                self._recurseSum(node.left, 10 * cur_num + node.val)
            if node.right is not None:
                self._recurseSum(node.right, 10 * cur_num + node.val)

This site is open source. Improve this page.