129. Sum Root to Leaf Numbers

Problem Statement

link: https://leetcode.com/problems/sum-root-to-leaf-numbers/ https://leetcode.cn/problems/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 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:

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

Input: root = [4,9,0,5,1] Output: 1026

Solution Approach

The solution leverages depth-first traversal to construct and sum numbers from the root to each leaf.

Algorithm

1. Initialization: Begin with a running total n as we traverse from the root.
2. DFS with Accumulation: For each node, modify the current number (n = n * 10 + node.val) and recursively traverse left and right children.
3. Leaf Check: At a leaf (no children), return the current path’s number. If not a leaf, return the combined sum from both subtrees.
4. Final Sum: The initial function call yields the sum of all root-to-leaf numbers.

Implement

    class Solution:
      def sumNumbers(self, root: Optional[TreeNode]) -> int:
          def getSum(node, n):
              if not node:
                  return 0
              n = n * 10 + node.val
              if not node.left and not node.right:
                  return n
              else:
                  return getSum(node.left, n) + getSum(node.right, n)
          return getSum(root, 0)
 

    
    

Twitter  facebook  Email