LEETCODE 113. 路径总和 II

LEETCODE 113. 路径总和 II

题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树,以及目标和 sum = 22,

5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:

[
[5,4,11,2],
[5,8,4,5]
]

题目地址
中文版
英文版

代码实现

class Solution(object):
	def pathSum(self, root, sum):
		"""
		:type root: TreeNode
		:type sum: int
		:rtype: List[List[int]]
		"""
		if(not root):
			return []
		res = []
		def dfs(root,arr,n):
			if root and (not root.left) and (not root.right):
				if(n+root.val == sum):
					tmp = arr+[root.val]
					res.append(list(tmp))
					return
			if root.left:
				dfs(root.left,arr+[root.val],n+root.val)
			if root.right:
				dfs(root.right,arr+[root.val],n+root.val)
		dfs(root,[],0)
		return res
                                                                                
2 次阅读

发表评论

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