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

标签: 树 深度优先搜索 二叉树

难度: Medium

给你一个二叉树的根节点 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

Submission

运行时间: 44 ms

内存: 15 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    s = 0

    def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0

        def dfs(root, k):
            if root is None:
                return
            if k == "0":
                k = str(root.val)
            else:
                k += str(root.val)
            if root.left is None and root.right is None:
                self.s += int(k)
            dfs(root.left, k)
            dfs(root.right, k)

        dfs(root, "0")
        return self.s

Explain

这个题解采用了深度优先搜索（DFS）的思路来解决问题。具体来说，它定义了一个辅助函数 dfs，用于递归遍历二叉树的每个节点。在遍历过程中，它维护了一个字符串 k，用于记录从根节点到当前节点的路径所表示的数字。当遍历到叶子节点时，将 k 转换为整数并加到全局变量 s 上。最终，s 的值就是所有根到叶子节点路径代表的数字之和。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    s = 0

    def sumNumbers(self, root: TreeNode) -> int:
        if root is None:
            return 0

        def dfs(root, k):
            if root is None:
                return
            if k == "0":
                k = str(root.val)
            else:
                k += str(root.val)
            # 如果当前节点是叶子节点，将路径代表的数字加到 s 上
            if root.left is None and root.right is None:
                self.s += int(k)
            # 递归遍历左子树
            dfs(root.left, k)
            # 递归遍历右子树
            dfs(root.right, k)

        dfs(root, "0")
        return self.s

Explore

在 DFS 中使用字符串来累积路径值而不是整数的主要原因是简化了数字的连接操作。使用整数时，每次追加一个新的数字需要计算 `current = current * 10 + new_digit`，这在递归中稍微复杂一些，特别是在递归返回时，需要逆操作来恢复原始的整数值。而使用字符串，简单的字符串连接 `current_str += str(new_digit)` 更直观且易于管理。但实际上，使用整数计算通常更高效，因为整数操作比字符串操作快，并且避免了最后的字符串到整数的转换。

处理空树的情况确实是必要的，因为题目的定义涵盖了所有可能的二叉树输入，包括空树。当根节点为空时，意味着树不存在任何节点，因此根到叶的路径和为0。这种特殊情况的处理确保了函数对于所有有效输入的健壮性。

直接将字符串转换为整数是一种简单直观的方法，但并非最高效。更高效的方法是在遍历过程中使用整数来累积路径值。这样，每向下遍历一层，可以通过 `current = current * 10 + root.val` 更新当前路径值，避免了字符串操作和最后的转换过程。这种方法在性能上更优，因为整数操作通常比字符串操作快，并且减少了类型转换的开销。

这种情况已经被考虑。在二叉树中，一个节点的值为0并不影响累积路径值的过程：即使值为0，它也会正常地被添加到路径字符串中，或者在使用整数累积时被计算。因此，无论是在路径中间还是作为叶子节点的值，0都会被正常处理，并准确地反映在最终的路径和中。