难度: 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运行时间: 56 ms
内存: 16.2 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
result = []
def dfs(root, path, k):
if root is None:
return
path.append(root.val)
if root.val == k and root.left is None and root.right is None:
result.append(list(path))
dfs(root.left, path, k-root.val)
dfs(root.right, path, k-root.val)
path.pop()
dfs(root, [], targetSum)
return result
该题采用深度优先搜索(DFS)的方法。从根节点开始，遍历整棵二叉树，并记录从根到当前节点的路径。当遍历到叶子节点，且路径上节点值的总和等于目标和时，将该路径加入结果列表。在递归回溯时，要从路径中删除当前节点，以便尝试其他路径。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
result = []
def dfs(root, path, k):
if root is None:
return
path.append(root.val)
# 如果当前节点是叶子节点且节点值等于目标和，则找到一条满足条件的路径
if root.val == k and root.left is None and root.right is None:
result.append(list(path))
# 递归遍历左子树和右子树
dfs(root.left, path, k-root.val)
dfs(root.right, path, k-root.val)
# 回溯时从路径中删除当前节点
path.pop()
dfs(root, [], targetSum)
return result
在递归函数中使用`path.append(root.val)`和`path.pop()`是为了记录和维护从根节点到当前节点的路径。这种操作称为回溯。当递归调用进入下一层时，`path.append`会添加当前节点的值到路径中。当从一个节点返回到其父节点时，`path.pop`会移除当前节点的值，这样路径就可以正确地反映从根节点到父节点的有效路径。这样的操作简化了路径管理，避免了额外的空间和复杂的路径复制操作，使代码更简洁、更高效。
这个条件确保了只有在叶子节点处才检查路径总和。在二叉树中，叶子节点定义为没有子节点的节点。此条件通过检查`root.left is None and root.right is None`来验证一个节点是否为叶子节点。如果这个条件在非叶子节点被满足，比如中间某个节点的路径总和已经等于`k`，但该节点下还有其他子节点，则可能会错过包含更完整路径的正确解，因为实际上这条路径并没有结束。
如果所有节点的值都大于0，而目标和`targetSum`是一个负数，那么算法将不会找到任何匹配的路径。因为随着树的深入，路径的总和只会增加，不可能达到一个负数的目标和。因此，`dfs`函数在这种情况下会遍历整个树，但不会在`result`中添加任何路径，最终返回一个空的列表。
深度优先搜索（DFS）和广度优先搜索（BFS）都可以用来解决路径总和问题，但它们各有优缺点。DFS通过递归实现，代码相对简洁，且由于它深入到叶节点，可以立即判断路径总和是否符合条件。其缺点是在最坏情况下可能会持有较深的调用堆栈。相比之下，BFS使用队列实现，可以逐层处理节点，有助于快速排除一些不可能的路径，特别是在路径和过大时。但BFS需要额外的空间来存储每一层的节点和路径，对于路径总和问题，可能效率不如DFS。