【leetcode100】路径总和Ⅲ

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