Sum Root to Leaf Numbers
Problem
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.
Carry a running integer down the recursion: cur = cur · 10 + node.val. At a leaf, add cur to the total. Otherwise recurse into both children.
level-order: [4, 9, 0, 5, 1]1026def sum_numbers(root):
def dfs(node, cur):
if node is None: return 0
cur = cur * 10 + node.val
if node.left is None and node.right is None:
return cur
return dfs(node.left, cur) + dfs(node.right, cur)
return dfs(root, 0)function sumNumbers(root) {
function dfs(node, cur) {
if (!node) return 0;
cur = cur * 10 + node.val;
if (!node.left && !node.right) return cur;
return dfs(node.left, cur) + dfs(node.right, cur);
}
return dfs(root, 0);
}class Solution {
public int sumNumbers(TreeNode root) { return dfs(root, 0); }
int dfs(TreeNode node, int cur) {
if (node == null) return 0;
cur = cur * 10 + node.val;
if (node.left == null && node.right == null) return cur;
return dfs(node.left, cur) + dfs(node.right, cur);
}
}int dfs(TreeNode* node, int cur) {
if (!node) return 0;
cur = cur * 10 + node->val;
if (!node->left && !node->right) return cur;
return dfs(node->left, cur) + dfs(node->right, cur);
}
int sumNumbers(TreeNode* root) { return dfs(root, 0); }Explanation
Every path from the root to a leaf spells out a decimal number, and we want the sum of all of them. We build each number digit by digit while walking down the tree.
The helper dfs(node, cur) carries cur, the number formed so far. At each node we do cur = cur * 10 + node.val, which shifts the existing digits one place to the left and appends the new digit on the right — exactly how you read a number.
When we hit a leaf, cur is the finished number for that path, so we return it. For an internal node we recurse into both children and add their totals, which adds up every root-to-leaf number.
Example: [4,9,0,5,1]. The paths are 4→9→5 = 495, 4→9→1 = 491, and 4→0 = 40. Summing gives 495 + 491 + 40 = 1026.
Each node is visited once, so the runtime is O(n).