# 1022. Sum of Root To Leaf Binary Numbers 从根到叶的二进制数之和

@TOC

## # 题目描述

Given a binary tree, each node has value `0` or `1`. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is `0 -> 1 -> 1 -> 0 -> 1`, then this could represent `01101` in binary, which is `13`.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.

Return the sum of these numbers modulo `10^9 + 7`.

Example 1:

``````Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
``````

Note:

1. The number of nodes in the tree is between 1 and 1000.
2. `node.val` is `0` or `1`.

## # 解题方法

### # DFS

Python的整数不会越界，这题中每经历过一个节点，就把之前的路径*2 + 当前的节点值当做路径表示的整数。

Python代码如下：

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

class Solution(object):
def sumRootToLeaf(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
self.res = 0
self.dfs(root, root.val)
return self.res

def dfs(self, root, preSum):
if not root.left and not root.right:
self.res = (self.res + preSum) % (10 ** 9 + 7)
return
if root.left:
self.dfs(root.left, preSum * 2 + root.left.val)
if root.right:
self.dfs(root.right, preSum * 2 + root.right.val)
``````

## # 日期

2019 年 4 月 7 日 —— 周赛bug了3次。。