题目描述:
思路:
可以采用递归+回溯。递归访问左->右->根节点并记录路径。到叶节点后,计算数字并相加。
代码:
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
res = 0
path = []
def backtrace(root):
nonlocal res
if not root: return # 节点空则返回
path.append(root.val)
if not root.left and not root.right: # 遇到了叶子节点
res += get_sum(path)
if root.left: # 左子树不空
backtrace(root.left)
if root.right: # 右子树不空
backtrace(root.right)
path.pop()
def get_sum(arr):
s = 0
for i in range(len(arr)):
s = s * 10 + arr[i]
return s
backtrace(root)
return res