Time: 2019-08-11
题目描述
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
这和前面的112.路径之和，113.路径之和II都是一种类型的题目，唯一的区别在于遍历过程中要做一些什么操作，要带什么参数进入到下一层的递归。
本题只用带上curSum即可，然后边递归边计算从根到叶子结点的和，总和用的是实例变量，用于跟踪全局大小。
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
self.result = 0
self.dfs(root, 0)
return self.result
def dfs(self, root, curSum):
if root == None:
return
# 到递归边界叶子结点
if root.left == None and root.right == None:
self.result += curSum * 10 + root.val
return
self.dfs(root.left, curSum * 10 + root.val)
self.dfs(root.right, curSum * 10 + root.val)
时空复杂度
时间复杂度：O(n)
空间复杂度：O(1)
相似题目
- Leetcode 112
- Leetcode 113
END.
