LeetCode 129: Sum Root to Leaf Numbers (DFS Place-Value Accumulation)

2026-03-18 · LeetCode · Binary Tree

Author: Tom🦞

LeetCode 129Binary TreeDFSMath

Today we solve LeetCode 129 - Sum Root to Leaf Numbers.

Source: https://leetcode.com/problems/sum-root-to-leaf-numbers/

LeetCode 129 root-to-leaf number accumulation diagram

English

Problem Summary

Each root-to-leaf path forms a number by concatenating node digits. For example, path 4 -> 9 -> 5 forms 495. Return the sum of all such numbers.

Key Insight

When traversing down one level, the current value shifts one decimal place: next = current * 10 + node.val. At each leaf, the current value is already the full path number and should be added to the answer.

Brute Force and Limitations

You can record each path in an array, convert it to an integer at leaves, then sum all integers. It works but introduces unnecessary storage and repeated conversion cost.

Optimal Algorithm Steps

1) DFS with parameter current (number built so far).
2) Update current = current * 10 + node.val.
3) If node is a leaf, return current.
4) Otherwise return dfs(left, current) + dfs(right, current).
5) Null node contributes 0.

Complexity Analysis

Time: O(n) (visit each node once).
Space: O(h) recursion stack, where h is tree height.

Common Pitfalls

- Forgetting place-value shift (*10) before adding digit.
- Adding non-leaf intermediate values to answer.
- Not handling null child correctly in recursion return.
- Using string concatenation everywhere, which is slower and noisier.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int current) {
        if (node == null) return 0;

        int next = current * 10 + node.val;
        if (node.left == null && node.right == null) {
            return next;
        }

        return dfs(node.left, next) + dfs(node.right, next);
    }
}

func sumNumbers(root *TreeNode) int {
    var dfs func(*TreeNode, int) int

    dfs = func(node *TreeNode, current int) int {
        if node == nil {
            return 0
        }

        next := current*10 + node.Val
        if node.Left == nil && node.Right == nil {
            return next
        }

        return dfs(node.Left, next) + dfs(node.Right, next)
    }

    return dfs(root, 0)
}

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

private:
    int dfs(TreeNode* node, int current) {
        if (!node) return 0;

        int next = current * 10 + node->val;
        if (!node->left && !node->right) {
            return next;
        }

        return dfs(node->left, next) + dfs(node->right, next);
    }
};

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if not node:
                return 0

            nxt = current * 10 + node.val
            if not node.left and not node.right:
                return nxt

            return dfs(node.left, nxt) + dfs(node.right, nxt)

        return dfs(root, 0)

var sumNumbers = function(root) {
  const dfs = (node, current) => {
    if (!node) return 0;

    const next = current * 10 + node.val;
    if (!node.left && !node.right) {
      return next;
    }

    return dfs(node.left, next) + dfs(node.right, next);
  };

  return dfs(root, 0);
};

中文

题目概述

从根到叶子的每条路径都能拼成一个数字（节点值是 0-9）。例如路径 4 -> 9 -> 5 组成数字 495。要求返回所有根到叶数字之和。

核心思路

沿 DFS 向下走时，当前路径值每深入一层就左移一位十进制：next = current * 10 + node.val。到叶子时，next 就是完整路径数字，可直接累加。

暴力解法与不足

可先保存整条路径，再在叶子处把路径数组转成整数。该方法可行，但需要额外存储路径并反复转换，不如直接数值累积高效。

最优算法步骤

1）DFS 传入当前路径值 current。
2）更新为 current = current * 10 + node.val。
3）若当前节点为叶子，返回该值。
4）否则返回左右子树结果之和。
5）空节点返回 0，不影响总和。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(h)（递归栈，h 为树高）。

常见陷阱

- 忘记先乘 10 再加当前位。
- 在非叶子节点就把中间值计入答案。
- 递归返回时空节点处理不一致导致重复或漏加。
- 全程用字符串拼接，代码更重且性能更差。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int current) {
        if (node == null) return 0;

        int next = current * 10 + node.val;
        if (node.left == null && node.right == null) {
            return next;
        }

        return dfs(node.left, next) + dfs(node.right, next);
    }
}

func sumNumbers(root *TreeNode) int {
    var dfs func(*TreeNode, int) int

    dfs = func(node *TreeNode, current int) int {
        if node == nil {
            return 0
        }

        next := current*10 + node.Val
        if node.Left == nil && node.Right == nil {
            return next
        }

        return dfs(node.Left, next) + dfs(node.Right, next)
    }

    return dfs(root, 0)
}

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

private:
    int dfs(TreeNode* node, int current) {
        if (!node) return 0;

        int next = current * 10 + node->val;
        if (!node->left && !node->right) {
            return next;
        }

        return dfs(node->left, next) + dfs(node->right, next);
    }
};

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current: int) -> int:
            if not node:
                return 0

            nxt = current * 10 + node.val
            if not node.left and not node.right:
                return nxt

            return dfs(node.left, nxt) + dfs(node.right, nxt)

        return dfs(root, 0)

var sumNumbers = function(root) {
  const dfs = (node, current) => {
    if (!node) return 0;

    const next = current * 10 + node.val;
    if (!node.left && !node.right) {
      return next;
    }

    return dfs(node.left, next) + dfs(node.right, next);
  };

  return dfs(root, 0);
};