目录
一、题目内容
二、解题思路
三、代码
一、题目内容
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 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 = xself.left = Noneself.right = Nonedef __repr__(self):return str(self.val)class Solution:def pathSum(self, root: TreeNode, sum_num: int) -> list:if not root:return []self.sum = sum_numself.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.resif __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 = 22s = Solution()ans = s.pathSum(a, sum_num)print(ans)