題目鏈接
難度：中等 ??????類型：
給定一個二叉樹烫沙，它的每個結點都存放一個 0-9 的數字莺掠，每條從根到葉子節(jié)點的路徑都代表一個數字筛欢。
例如，從根到葉子節(jié)點路徑 1->2->3 代表數字 123榨咐。
計算從根到葉子節(jié)點生成的所有數字之和。
說明: 葉子節(jié)點是指沒有子節(jié)點的節(jié)點谴供。
示例1
輸入: [1,2,3]
1
/
2 3
輸出: 25
解釋:
從根到葉子節(jié)點路徑 1->2 代表數字 12.
從根到葉子節(jié)點路徑 1->3 代表數字 13.
因此块茁，數字總和 = 12 + 13 = 25.
示例2
輸入: [4,9,0,5,1]
4
/
9 0
/
5 1
輸出: 1026
解釋:
從根到葉子節(jié)點路徑 4->9->5 代表數字 495.
從根到葉子節(jié)點路徑 4->9->1 代表數字 491.
從根到葉子節(jié)點路徑 4->0 代表數字 40.
因此，數字總和 = 495 + 491 + 40 = 1026.
解題思路
從上到下遍歷二叉樹桂肌，逐節(jié)點進行num*10+root.val計算
代碼實現
# 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 sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
self.res = 0
def calc(root, num):
if not root.left and not root.right:
self.res += num*10+root.val
if root.left:
calc(root.left, num*10+root.val)
if root.right:
calc(root.right, num*10+root.val)
calc(root, 0)
return self.res
