1、题目描述
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
2、初始思路
2.1 题目分析
计算二叉树中路径和等于给定目标值 targetSum 的路径数量。
2.1.1 前缀和
前缀和是指从根节点到当前节点的路径上所有节点值的累加和。例如：如果路径是 1 -> 2 -> 3，那么前缀和依次为 1、3（1+2）、6（1+2+3）。
前缀和的核心思想是：
如果从根节点到节点 A 的前缀和为 s1，从根节点到节点 B 的前缀和为 s2，那么从节点 A 到节点 B 的路径和就是 s2 - s1。
因此，如果我们想要找到路径和等于 targetSum 的路径，只需要找到满足 s2 - s1 = targetSum 的前缀对 (s1, s2)。
2.1.2 字典存储
哈希表 cnt 用于记录从根节点到当前节点的路径上，各个前缀和出现的次数。它的作用是：
在遍历时，快速检查是否存在一个前缀和 s1，使得 s2 - s1 = targetSum。如果存在这样的 s1，则说明从某个节点到当前节点的路径和等于 targetSum。
具体来说：
cnt[s] 表示前缀和 s 出现的次数。当我们计算到当前节点的前缀和 s2 时，检查 s2 - targetSum 是否在 cnt 中。如果存在，则说明有 cnt[s2 - targetSum] 条路径满足条件。
2.2 思路
使用前缀和+字典存储
# 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: Optional[TreeNode], targetSum: int) -> int:
ans = 0
cnt = defaultdict(int)
cnt[0] = 1
def dfs(node,s):
if not node:
return
#nonlocal用于修改外部函数中的变量
nonlocal ans
#s 代表从根节点到当前节点的前缀和，cnt[s]表示前缀和为s的个数
s += node.val
ans += cnt[s - targetSum]
cnt[s] += 1
dfs(node.left,s)
dfs(node.right,s)
cnt[s] -= 1
dfs(root,0)
return ans