给定一个二叉树和一个值，请找出所有的根节点到叶子节点的节点值之和等于 的路径，

返回这些路径的集合。

思路：

递归遍历二叉树，从根节点到叶子节点统计节点值之和，如果等于给定值就把该路径添加到结果集合中。需要注意的是，在递归遍历过程中，需要维护一个路径 list 来记录当前的路径，每次递归到左右子节点时，需要将当前节点值加入路径 list 中，递归结束后，需要将当前节点从路径 list 中移除。

时间复杂度：O(n)，空间复杂度：O(logn)（二叉树为平衡树）。

Python 代码：

相关问题

给定一个二叉树root和一个值 sum： （1）判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径； （2）若有找出二叉树中结点值的和为sum的所有路径。

### 回答1：
这个问题需要我们构建一棵二叉树，其中根节点为root，每个节点都有一个值。回答问题分为两部分：

1. 判断是否有从根节点到叶子节点的路径值之和等于sum。我们可以采用递归的方式，遍历每个节点，如果当前节点是叶子节点且路径值之和等于sum，则返回True，否则继续遍历其左右子树。如果最终所有的叶子节点都遍历完了，仍然没有找到路径值之和等于sum的，则返回False。

2. 如果存在从根节点到叶子节点的路径值之和等于sum，则需要找出这样的路径。可以采用回溯法，在递归的过程中记录下遍历的路径，如果找到了路径值之和等于sum的路径，则输出该路径。

### 回答2：
这个问题可以用深度优先搜索（DFS）算法来解决，我们从根节点开始遍历二叉树，遍历到一个节点时，我们将该节点的值加入当前路径的节点值之和中，并在路径列表中加入该节点。如果该节点是叶子节点并且当前路径的节点值之和等于sum，那么我们就找到了一条符合条件的路径，将其加入结果列表中。

如果该节点不是叶子节点，我们就分别遍历它的左子树和右子树，直到找到一条符合条件的路径或者遍历完整棵树。每次遍历完当前节点后，我们就将该节点从路径中删除，并继续遍历它的父节点的另一个子节点。

具体实现见下面的代码：

class Solution:
    def pathSum(self, root, sum):
        res = []
        def dfs(node, path, total):
            if not node:
                return
            path.append(node.val)
            total += node.val
            if not node.left and not node.right and total == sum:
                res.append(path[:])
            dfs(node.left, path, total)
            dfs(node.right, path, total)
            path.pop()
        dfs(root, [], 0)
        return res

这段代码中，我们首先定义了一个空的结果列表 res 和一个 dfs 函数。函数 dfs 的参数包括当前节点 node，当前路径 path 和当前路径的节点值之和 total。我们首先判断当前节点是否为空，为空则直接返回。

然后将当前节点的值加入路径 path 中，并将当前节点的值加入总和 total 中。接着判断当前节点是否是叶子节点并且当前路径的节点值之和等于 sum，如果是，则将当前路径加入结果列表 res 中。

最后，我们对当前节点的左子树和右子树分别使用 dfs 函数进行遍历，并在遍历后将当前节点从路径 path 中删除。

在函数 pathSum 中，我们调用 dfs 函数，并将根节点和一个空路径以及节点值之和为 0 作为参数传入。最后返回结果列表 res。

### 回答3：
题目描述：

给定一个二叉树root和一个值 sum：

（1）判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径；

（2）若有找出二叉树中结点值的和为sum的所有路径。

解题思路：

对于第一问，我们可以采用递归的方式，对于每个节点，分别计算它的左子树和右子树是否有满足要求的路径。如果当前节点为叶子节点，且节点值等于sum，说明找到了一条满足要求的路径。

对于第二问，我们可以采用深度优先搜索（DFS）的方式，对于每个节点，先将它加入当前路径中，然后对它的左右子树进行操作。当搜索到叶子节点时，判断当前路径是否满足要求，如果满足则将当前路径加入结果集。最后将当前节点从路径中删除，返回到父节点，继续搜索。

代码实现：

（1）判断是否存在满足要求的路径

def hasPathSum(root, sum):
    if not root:
        return False
    if not root.left and not root.right:
        return root.val == sum
    else:
        return hasPathSum(root.left, sum - root.val) or hasPathSum(root.right, sum - root.val)

（2）找出所有满足要求的路径

def pathSum(root, sum):
    res = []
    path = []
    def dfs(root, sum):
        if not root:
            return
        path.append(root.val)
        sum -= root.val
        if not root.left and not root.right and sum == 0:
            res.append(path[:])
        dfs(root.left, sum)
        dfs(root.right, sum)
        path.pop() # 回溯，将当前节点从路径中删除
    dfs(root, sum)
    return res

python牛客84二叉树和为某一值的路径3

题目要求：给定一个二叉树和一个整数target，找出所有从根节点到叶子节点路径之和等于target的路径。

解题思路：可以使用深度优先搜索（DFS）的方法来解决该问题。首先定义一个辅助函数来进行递归搜索，该辅助函数的参数包括当前节点、当前路径、当前路径的和以及目标和。在搜索过程中，需要维护一个数组来保存当前节点到根节点的路径。搜索过程如下：
1. 如果当前节点为空，则返回。
2. 将当前节点的值添加到当前路径中。
3. 将当前节点的值累加到当前路径的和中。
4. 如果当前节点是叶子节点，且当前路径的和等于目标和，则将当前路径添加到结果中。
5. 递归地搜索当前节点的左子树和右子树，并传递更新后的当前路径和当前路径的和。

最后，在主函数中调用辅助函数，并返回结果即可。

以下是题目的完整代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def pathSum(root, target):
    def dfs(node, path, path_sum, target, res):
        if not node:
            return
        path.append(node.val)
        path_sum += node.val
        if not node.left and not node.right:  # 当前节点是叶子节点
            if path_sum == target:
                res.append(path[:])  # 注意需要复制一份path，否则会出现问题
        dfs(node.left, path, path_sum, target, res)
        dfs(node.right, path, path_sum, target, res)
        path.pop()  # 回溯到父节点，去掉当前节点
        path_sum -= node.val

    res = []
    dfs(root, [], 0, target, res)
    return res

这样就能找出所有满足路径和等于目标和的路径了。