难度: Medium
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
[0, 5000] 内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/
运行时间: 52 ms
内存: 16.1 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def dfs(node, tar):
if node is None:
return
path.append(node.val)
tar -= node.val
if node.left is None and node.right is None and tar == 0:
res.append(list(path))
dfs(node.left, tar)
dfs(node.right, tar)
path.pop()
dfs(root, sum)
return res
该题解采用了深度优先搜索（DFS）的方法来遍历二叉树，查找所有从根节点到叶子节点的路径，使得路径上的节点值之和等于目标和。使用一个列表 path 来记录当前路径上的节点值，每当访问一个节点时，将该节点的值加入 path。当到达叶子节点且路径上节点值之和等于目标和时，将 path 的一个副本加入结果列表 res 中。之后回溯，从 path 中移除最后一个节点值，继续探索其他路径。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
res, path = [], []
def dfs(node, tar):
if node is None:
return
path.append(node.val) # 将当前节点值加入路径
tar -= node.val # 更新剩余目标和
if node.left is None and node.right is None and tar == 0:
res.append(list(path)) # 找到一条符合条件的路径
dfs(node.left, tar) # 深度优先搜索左子树
dfs(node.right, tar) # 深度优先搜索右子树
path.pop() # 回溯，移除路径上的最后一个节点值
dfs(root, sum)
return res
在算法中，我们通过检查当前节点是否为叶子节点（即没有左孩子和右孩子）来确保只考虑从根到叶的路径。只有当节点是叶子节点且路径上的节点值之和等于目标和时，才会将该路径添加到结果列表中。这样可以避免将从根到中间节点的路径错误地纳入考虑。
在深度优先搜索中，`path.pop()`操作是在递归函数返回之前执行的，它删除的是当前递归中最后添加到路径中的节点值。由于递归的堆栈性质，每次递归调用完成后，`path.pop()`确保移除的是当前递归环境下添加的节点，这样每个递归实例的路径都是独立而准确的，不会相互影响。
如果输入的二叉树是空树（null），算法在初始的dfs调用中就会检测到节点为null，并立即返回。因此，不会进行任何路径的添加操作，结果列表`res`将保持为空。最终算法返回的结果是一个空列表，这表明没有可用的路径满足条件，这是正确的处理方式。
当树中包含负数节点值时，算法仍然有效。由于目标和可以是任意整数，负数节点值的存在允许在计算路径总和时进行上下调整。这意味着算法能够灵活地处理各种情况，包括节点值有正有负的情况。因此，即使存在负数节点值，算法依然能够正确地搜索到所有符合条件的从根到叶的路径。