本文主要是介绍leetcode-129. 求根到叶子节点数字之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]1/ \2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.
示例 2:
输入: [4,9,0,5,1]4/ \9 0/ \
5 1
输出: 1026
解释:
从根到叶子节点路径 4->9->5 代表数字 495.
从根到叶子节点路径 4->9->1 代表数字 491.
从根到叶子节点路径 4->0 代表数字 40.
因此，数字总和 = 495 + 491 + 40 = 1026.
解题思路
用深度优先遍历，路径的过程中就保存当前这条路径的数字和，当碰到叶子节点时，累加到总和上即可。
时间复杂度是o(n)
代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:def sumNumbers(self, root: TreeNode) -> int:if not root:return 0stack = [(root, 0)]cur_num = 0cur_sum = 0while stack:p, stat = stack.pop()if stat == 0:stack.append((p, 1))cur_num = cur_num * 10 + p.valif p.left:stack.append((p.left, 0))if p.right:stack.append((p.right, 0))else:if (not p.left) and (not p.right):cur_sum += cur_numcur_num = (cur_num - p.val) / 10return int(cur_sum)
这篇关于leetcode-129. 求根到叶子节点数字之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
