难度: Medium
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
[0,1000]-109 <= Node.val <= 109 -1000 <= targetSum <= 1000 注意：本题与主站 437 题相同：https://leetcode-cn.com/problems/path-sum-iii/
运行时间: 34 ms
内存: 16.5 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) -> int:
self.ans = 0
Sumpath = {0:1}
def dfs(node, sums):
sums += node.val
if (sums - targetSum) in Sumpath:
self.ans += Sumpath[sums - targetSum]
if sums not in Sumpath:
Sumpath[sums] = 1
else:
Sumpath[sums] += 1
if node.left:
dfs(node.left, sums)
if node.right:
dfs(node.right, sums)
Sumpath[sums] -= 1
if not root:
return 0
dfs(root, 0)
return self.ans
该题解采用了深度优先搜索(DFS)和哈希表来解决问题。首先，我们递归地遍历树的每一个节点，同时维护当前路径的累计和。哈希表`Sumpath`用于存储每个节点到根节点路径上的累计和及其出现的次数。对于每个节点，我们检查`当前累计和 - 目标和`是否已经在哈希表中，如果存在，则说明我们找到了一个有效路径。在递归进入左右子节点之前，更新哈希表以包含当前累计和。在从子节点返回后，为了不影响其他路径，需要将当前累计和的计数减一，以防止它干扰其他路径的计算。这种方法有效地利用了前缀和的概念，即使用累计和减去目标值来快速检查是否存在符合条件的路径。
时间复杂度: 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) -> int:
self.ans = 0 # 用于记录路径总数的变量
Sumpath = {0:1} # 哈希表，记录各路径和出现的次数，初始化为0出现一次
def dfs(node, sums):
if not node:
return # 空节点直接返回
sums += node.val # 更新当前路径和
if (sums - targetSum) in Sumpath:
self.ans += Sumpath[sums - targetSum] # 找到有效路径
if sums not in Sumpath:
Sumpath[sums] = 1
else:
Sumpath[sums] += 1
if node.left:
dfs(node.left, sums) # 递归左子树
if node.right:
dfs(node.right, sums) # 递归右子树
Sumpath[sums] -= 1 # 回溯，撤销当前节点对路径和的影响
if not root:
return 0 # 空树直接返回0
dfs(root, 0) # 从根节点开始递归
return self.ans # 返回路径总数
在递归遍历过程中，每到达一个新的节点，我们都会更新哈希表`Sumpath`以记录当前路径的累计和及其出现次数。这种更新操作包括插入新的键值对和更新已有键的值，通常这些操作的时间复杂度是O(1)。然而，由于这些操作需要在每个节点处执行，因此整体上会对算法的性能产生影响，尤其是当树的大小非常大时。每次更新哈希表都涉及到内存的读写，这在数据量大时可能会成为性能瓶颈。此外，频繁的更新操作可能会影响哈希表的负载因子，进而影响整体性能。总的来说，虽然每次操作的时间复杂度较低，但频繁操作仍可能导致较高的累计时间消耗，尤其是在树的结构复杂或节点数目极多时。
这个操作是回溯的一部分，是必要的以确保每个节点退出递归后不会影响其他路径的计算。在深度优先搜索中，当探索一个节点的所有子节点后，我们需要从总路径和中移除当前节点的值，以反映回到了之前的状态。如果我们不减少哈希表中当前累计和的计数，那么当开始探索其他兄弟节点或父节点的其他路径时，这个累计和仍会错误地反映在哈希表中，这可能导致错误地计算出额外的路径匹配。因此，减一操作是为了保持算法的正确性和防止对未来路径探索的干扰。
初始设置`0:1`是为了处理从根节点到当前节点路径累计和正好等于目标和的情况。这种设置相当于提供了一个虚拟的前缀和，表示在任何实际节点之前，有一个和为0的路径。例如，如果从根节点到某个节点的路径和恰好等于目标和，那么根据哈希表中的记录，当前累计和减目标和等于0，查看哈希表我们会发现0已经被记录了1次，这意味着存在一条路径（从根到当前节点）其和为目标和。因此，这种初始化方式是为了方便处理包含根节点的那些路径，其和恰好等于目标和的情况。