leetcode_113. 路径总和 II
【摘要】 目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
 ...
目录
一、题目内容
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:[
[5,4,11,2],
[5,8,4,5]
]
二、解题思路
前序遍历，如果到达叶子结点且tmp的和为sum就加入到结果集中。
三、代码
-
# Definition for a binary tree node.
-
class TreeNode:
-
def __init__(self, x):
-
self.val = x
-
self.left = None
-
self.right = None
-
-
def __repr__(self):
-
return str(self.val)
-
-
class Solution:
-
def pathSum(self, root: TreeNode, sum_num: int) -> list:
-
if not root:
-
return []
-
self.sum = sum_num
-
self.res = []
-
def dfs(root, tmp):
-
if sum(tmp) == self.sum and root.left is None and root.right is None:
-
self.res.append(tmp)
-
if root.left:
-
dfs(root.left, tmp + [root.left.val])
-
if root.right:
-
dfs(root.right, tmp + [root.right.val])
-
dfs(root, [root.val])
-
return self.res
-
-
-
if __name__ == '__main__':
-
a = TreeNode(5)
-
a.left = TreeNode(4)
-
a.right = TreeNode(8)
-
a.left.left = TreeNode(11)
-
a.right.left = TreeNode(13)
-
a.right.right = TreeNode(4)
-
a.left.left.left = TreeNode(7)
-
a.left.left.right = TreeNode(2)
-
a.right.right.left = TreeNode(5)
-
a.right.right.right = TreeNode(1)
-
sum_num = 22
-
-
s = Solution()
-
ans = s.pathSum(a, sum_num)
-
print(ans)
-
文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。
原文链接：nickhuang1996.blog.csdn.net/article/details/108810745
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）