⚡Flashcard Drill➔
NeetCode #450LC-129MediumTrees
← Back to All Problems

#450 · #129 · Sum Root to Leaf Numbers(求根节点到叶节点数字之和)

📌 Problem Statement & Constraints

You are given the root of a binary tree containing digits from 0 to 9. Each root-to-leaf path represents a number formed by concatenating the digits. Return the total sum of all such numbers. Constraints: the number of nodes is in [1, 1000], 0 <= Node.val <= 9, the depth is at most 10.

💡 Core Algorithmic Approaches

  1. Carry the number built so far down the recursion: cur = cur * 10 + node.val.
  2. At a leaf, the accumulated value is a complete number, so return it.
  3. For internal nodes, return the sum of the two children's results.
  4. The leaf test must be not node.left and not node.right, since a single-child node does not end a number.

💻 Benchmark Python3 Implementation

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], cur: int) -> int:
            if not node:
                return 0
            cur = cur * 10 + node.val      # append the digit
            if not node.left and not node.right:
                return cur                 # leaf -> the number is complete
            return dfs(node.left, cur) + dfs(node.right, cur)

        return dfs(root, 0)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Treating a single-child node as a leaf: the number continues through the existing child.
  • Passing cur by reference and mutating it: the value must be local to each path, which the parameter passing handles.
  • Concatenating strings instead of arithmetic: workable but slower and unnecessary.
  • Forgetting the empty-tree case: the constraints guarantee at least one node, but the guard is cheap.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems