LeetCode 129. 求根节点到叶节点数字之和

约 4 分钟
文章信息 17 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 面试经典 150 题 腾讯 字节 华为 微软 亚马逊 美团 小米 百度 网易 快手
标签
深度优先搜索 树 二叉树

题目描述

✅ 129. 求根节点到叶节点数字之和

image-20260928191630349

image-20260928191630350

题意分析

每个节点保存一个 0 到 9 的数字，一条从根到叶子的路径会按经过顺序拼成一个十进制整数。要求把所有根到叶子路径对应的整数相加，返回总和。

这里累积的是拼接后的数字，不是沿路径把节点值直接相加。只有左右孩子都为空的节点才是叶子，到达内部节点时得到的只是一个尚未完成的数字；不同路径即使拼出相同数值，也要分别计入。

解法：DFS 传递路径数值

核心思路

[!blue]

沿一条路径向下走时，不需要先收集字符再转成整数。假设从根到当前节点的父节点已经拼成 prefix，把当前数字接在末尾，相当于让原数整体左移一位十进制位，再加入当前数字，即 current = prefix * 10 + node.val。

定义 dfs(node, prefix)：参数 prefix 表示到当前节点之前的路径数值；返回值则表示从当前子树继续走到所有叶子后，形成的完整路径数字之和。参数是单条路径的前缀，返回值是多条完整路径的合计，两者含义不能混淆。

若当前节点为空，这一侧不存在完整路径，返回 0。若当前节点是叶子，加入它之后恰好形成一条完整路径，直接返回 current。否则把同一个 current 分别传给左右孩子，再把两侧返回值相加。左右子树覆盖了所有后续路径且互不重复，因此逐层合并后得到的就是总和。

根节点之前还没有任何数字，所以从 dfs(root, 0) 开始。Java 和 Go 中这里的整数参数都按值传递，一个分支的递归不会改变另一个分支收到的前缀，因此无需共享路径数组，也不需要退出递归时再回滚数值。

解题步骤

  1. 从根节点开始 DFS，初始 prefix 为 0。
  2. 如果当前节点为空，返回 0，表示这一侧没有可贡献的根到叶路径。
  3. 计算 current = prefix * 10 + node.val，把当前节点数字接到已有前缀之后。
  4. 如果左右孩子都为空，当前路径完整，返回 current。
  5. 否则把 current 分别传入左右子树，返回两侧结果之和。

代码实现

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

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

        // 将当前数字接到已有路径数值末尾。
        int current = prefix * 10 + node.val;

        // 只有到叶子时才形成一条完整的根到叶数字。
        if (node.left == null && node.right == null) {
            return current;
        }

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

func sumNumbers(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, prefix int) int {
        if node == nil {
            return 0
        }

        // 将当前数字接到已有路径数值末尾。
        current := prefix*10 + node.Val
        // 只有到叶子时才形成一条完整的根到叶数字。
        if node.Left == nil && node.Right == nil {
            return current
        }

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

    return dfs(root, 0)
}

复杂度分析

设节点数为 n，树高为 h。

  • 时间复杂度：$O(n)$，每个节点只访问一次，拼接数字和合并返回值都只需要常数次运算。
  • 空间复杂度：$O(h)$，递归栈只保存当前根到节点的一条路径，最坏为 $O(n)$。

关键点总结

[!green]

  • 乘 10 再加当前数字，表示十进制拼接；直接相加求的是另一种路径和。
  • 路径前缀向下传递，完整路径的总和向上返回。
  • 叶子贡献一个完整数字，空子树贡献 0，内部节点只合并孩子的结果。

易错点总结

[!yellow]

  • 在每个节点都把 current 加入答案，会把尚未到达叶子的路径前缀也算进去。
  • 只要有一个孩子为空就判为叶子，会提前截断仍然能够向下延伸的路径，必须同时检查两个孩子。
  • 递归孩子时继续传旧的 prefix，会漏掉当前节点；应传已经拼入当前数字的 current。
  • 空节点不能返回传入的路径前缀，否则只有一个孩子的内部节点会额外贡献一条不存在的路径。

相似题目

题目 难度 关联与区别
112. 路径总和 简单 同样沿根到叶路径累积状态，本题每深入一层乘10再加数字，原题直接累加节点值。
1022. 从根到叶的二进制数之和 简单 同样把根路径当作一个数，本题十进制，原题二进制。
113. 路径总和 II 中等 回溯维护从根到当前节点的路径；本题逐层按十进制累加根到叶数字，该题复制并输出全部目标和叶路径。
257. 二叉树的所有路径 简单 回溯维护从根到当前节点的路径；本题逐层按十进制累加根到叶数字，该题输出所有根到叶的字符串路径。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/06191313
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！