题目大意
一棵树的每个节点都是0-9中的某一个数字，现在把从根节点到某一个叶子节点之间所有节点的数字依次连接起来组成一个新的数字。要求所有从根节点到叶子节点组成的数字的和。
解题思路
DFS, 到了新的叶子节点就将preSum*10+root.val
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution(object):
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return self._sumNumbers(root,0)
def _sumNumbers(self, root, preSum):
if not root:
return 0
preSum = preSum * 10 + root.val
if root.left == None and root.right == None:
return preSum
return self._sumNumbers(root.left, preSum) + self._sumNumbers(root.right, preSum)
|
总结