Problem 418193 · medium · Phase 04 Non-Linear Data Structures

Sum of Numbers Spelled by Root-to-Leaf Paths

binary tree · recursion · arithmetic

Every node of the tree holds a single digit 0-9. Each root-to-leaf path spells a decimal number (the root is the most significant digit). Return the sum of all those numbers. An empty tree sums to 0.

Examples

    4
   / \
  9   0
 / \
5   1

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

Input:  root = build_tree([1, 2, 3])
Output: 25

Constraints

  • 0 <= number of nodes <= 1000
  • 0 <= node.val <= 9
  • The tree depth is at most 12 in the visible tests, but Python integers make depth irrelevant.

Goals

  • Build a number digit by digit while descending
  • Combine results from both subtrees at a leaf boundary
Starting Python…