跳至主要內容

剑指 Offer II 049. 从根节点到叶节点的路径数字之和

ITCharge小于 1 分钟

剑指 Offer II 049. 从根节点到叶节点的路径数字之和open in new window

  • 标签:树、深度优先搜索、二叉树
  • 难度:中等

题目链接

题目大意

给定一个二叉树的根节点 root,树中每个节点都存放有一个 09 之间的数字。每条从根节点到叶节点的路径都代表一个数字。例如,从根节点到叶节点的路径是 1 -> 2 -> 3,表示数字 123

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

解题思路

使用深度优先搜索,记录下路径上所有节点构成的数字,使用 pretotal 保存下当前路径上构成的数字。如果遇到叶节点直接返回当前数字,否则递归遍历左右子树,并累加对应结果。

代码

class Solution:
    def dfs(self, root, pretotal):
        if not root:
            return 0
        total = pretotal * 10 + root.val
        if not root.left and not root.right:
            return total
        return self.dfs(root.left, total) + self.dfs(root.right, total)

    def sumNumbers(self, root: TreeNode) -> int:
        return self.dfs(root, 0)