LEETCODE 129. 求根到叶子节点数字之和

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.

题目地址
中文版
英文版

代码实现

class Solution(object):
	def sumNumbers(self, root):
		"""
		:type root: TreeNode
		:rtype: int
		"""
		if(not root):
			return 0
		res = []
		def dfs(root,n):
			if(root and not root.left and not root.right):
				res.append(n*10+root.val)
				return
			if root.left:
				dfs(root.left,n*10+root.val)
			if root.right:
				dfs(root.right,n*10+root.val)
		dfs(root,0)
		print res
		return sum(res)
                                                                   
0 次阅读

发表评论

电子邮件地址不会被公开。