Medium

Sum Root to Leaf Numbers

LAB

Given a binary tree encoded level-order with -100000 as null, treat each root-to-leaf path as a number and return their sum.

EXAMPLES

Example 1

Input
{
  "root": [
    1,
    2,
    3
  ]
}

Output
25

FUNCTION SHAPE

root: intArray→int

SOLUTION NOTE

Preorder traversal. Update the path number using 10 * path + root.val. Example: 123 = ((1) * 10 + 2) * 10 + 3. Use global state (res) updated during traversal.

Reveal reference solution +

pythonREFERENCE

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    res = 0

    def subtree(root, path):
        nonlocal res
        if not root: return
        v = 10 * path + root.val
        if not root.left and not root.right:
            res += v
            return
        subtree(root.left, v)
        subtree(root.right, v)

    subtree(root, 0)
    return res

TimeO(n)

SpaceO(h)

Open on LeetCode ↗