Sum of Numbers Formed by Root-to-Leaf Paths

medium tree dfs

Problem

Each node stores a digit 0–9. Each root-to-leaf path spells out a number (root digit is most significant). Sum every such number.

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.

Inputlevel-order: [4, 9, 0, 5, 1]

Output1026

Paths: 495, 491, 40 → sum 1026.

level-order, digits 0–9 ('_' for null)

def 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); }

Time: O(n) Space: O(h) recursion depth