# LeetCode: 129. Sum Root to Leaf Numbers

## 题目¶

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

```root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1
```

Return 3. The paths that sum to 8 are:

```1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11
```

## 解法¶

### 收集所有的 path 上节点的值，然后按照规则计算总和¶

```1 -> 2 -> 3 需要转换为数字 123：

1 * 10^2 + 2 * 10^1 + 3 * 10^0 = 123
```

```# 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:
def sumNumbers(self, root):
self._numbers = []
self._curr = []
total = 0

self._collect_numbers(root)
for numbers in self._numbers:
n = len(numbers) - 1
# [1, 2, 3] 需要转换为数字 123：
# 1 * 10^2 + 2 * 10^1 + 3 * 10^0
for number in numbers:
total = total + number * (10 ** n)
n = n - 1

def _collect_numbers(self, root):
if root is None:
return

if root.left is None and root.right is None:
curr = self._curr[:]
curr.append(root.val)
self._numbers.append(curr)
return

self._curr.append(root.val)

self._collect_numbers(root.left)
self._collect_numbers(root.right)

self._curr.pop()
```

### 在收集 root-to-leaf path 的过程中直接求和¶

• 1 -> 2 -> 3 转换为 123 的过程可以看成是，从上到下遍历的过程中每层都将上一层的结果乘 10 然后再加上当前节点的值： 1 -> 2 -> 3 -> 1 -> 1 * 10 + 2 -> (1 * 10 + 2) * 10 + 3 = 123
• 同时如果是一层一层的往下计算的话，还可以省去一些重复的计算步骤，把上层的结果传递给下层这样如果下层刚好有 leaf 节点就不需要从头到尾再重复计算一遍了。

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

self._collect(root, 0)

return self._total

def _collect(self, root, pre_deepth_sum):
if root is None:
return

new_deepth_sum = pre_deepth_sum * 10 + root.val

if root.left is None and root.right is None:
self._total += new_deepth_sum
return

# 将上层计算结果传递给下层
self._collect(root.left, new_deepth_sum)
self._collect(root.right, new_deepth_sum)
```