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
- Carry the number built so far down the recursion:
cur = cur * 10 + node.val. - At a leaf, the accumulated value is a complete number, so return it.
- For internal nodes, return the sum of the two children's results.
- 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
curby 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.