77.求根节点到叶节点数字之和

题目

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3] 输出：25

解释： - 从根到叶子节点路径 1->2 代表数字 12 - 从根到叶子节点路径 1->3 代表数字 13 - 因此，数字总和 = 12 + 13 = 25

示例 2：

• 输入：root = [4,9,0,5,1]
• 输出：1026

解释： - 从根到叶子节点路径 4->9->5 代表数字 495 - 从根到叶子节点路径 4->9->1 代表数字 491 - 从根到叶子节点路径 4->0 代表数字 40 - 因此，数字总和 = 495 + 491 + 40 = 1026

提示：

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

思路

核心思路: 如何把路径上的数字拼成整数？

没往下走一层，就把当前已经拼好的数字 * 10，再加上当前节点的值。

从根 4 出发：
  当前数 = 0
  到节点 4：当前数 = 0 × 10 + 4 = 4
  到节点 9：当前数 = 4 × 10 + 9 = 49
  到节点 5：当前数 = 49 × 10 + 5 = 495  → 叶子，收！

class Solution {
    fun sumNumbers(root: TreeNode?): Int {
        return dfs(root, 0)
    }

    private fun dfs(node: TreeNode?, currentNum: Int): Int {
        // 节点为空，返回 0，不贡献任何值
        if (node == null) return 0

        // 把当前节点的值拼接到数字后面
        val num = currentNum * 10 + node.`val`

        // 走到叶子节点，直接返回拼好的数字
        if (node.left == null && node.right == null) {
            return num
        }

        // 不是叶子，继续往左右两边走，把两边的结果加起来
        return dfs(node.left, num) + dfs(node.right, num)
    }
}

复杂度

• 时间复杂度: O(n)每个节点访问一次
• 空间复杂度: O(h)递归栈深度，h为树的高度

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!