LeetCode 第 437 题：路径总和 III（Path Sum III） 题目描述 给定一个二叉树的根节点 root ，和一个整数 targetSum ，你需要找到该二叉树里节点值之和等于 targetSum 的路径数目。 路径不需要从根节点开始，也不需要在叶子节点结束，但路径方向必须是向下的（只能从父节点到子节点）。 示例： 输入： root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出： 3 解释：存在三条路径，其节点值之和等于 8： 5 → 3 5 → 2 → 1 -3 → 11 解题思路 本题的关键在于路径不一定从根节点开始，因此需要遍历每个节点作为路径起点的情况。直接暴力枚举所有起点和终点会超时，需用前缀和优化。 步骤 1：理解问题本质 路径是向下的连续节点序列。 对于任意节点 B 到节点 C 的路径和，可表示为： sum(B到C) = prefixSum(C) - prefixSum(A) ，其中 A 是 B 的某个祖先节点。 若 sum(B到C) = targetSum ，则 prefixSum(C) - prefixSum(A) = targetSum ，即： prefixSum(A) = prefixSum(C) - targetSum 。 步骤 2：前缀和与哈希表 在深度优先搜索（DFS）过程中，记录从根节点到当前节点的路径和 currSum 。 用哈希表 prefixMap 存储当前路径上各前缀和的出现次数。 对于当前节点，检查 currSum - targetSum 在 prefixMap 中的出现次数，即为以当前节点为终点且满足条件的路径数目。 步骤 3：DFS 递归过程 递归函数定义 ： dfs(node, currSum) 返回以 node 为根的子树上满足条件的路径数目。 更新当前路径和 ： currSum += node.val 。 统计有效路径 ： 若 currSum - targetSum 存在于 prefixMap ，则累加对应次数到结果。 更新哈希表 ： 将 currSum 加入 prefixMap ，然后递归左右子树。 回溯 ： 在返回前将 currSum 从 prefixMap 中减 1（避免影响其他分支）。 步骤 4：初始化和细节 初始化 prefixMap 时需包含 {0: 1} ，表示路径和为 0 的情况（即空路径）。 通过回溯确保哈希表只记录当前路径的前缀和。 示例推导 以示例 root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 为例： 从根节点 10 开始， currSum 变化：10 → 15 → 18 → 21... 当走到节点 5 时， currSum = 15 ，检查 15 - 8 = 7 在 prefixMap 中不存在。 走到节点 3 时， currSum = 18 ，检查 18 - 8 = 10 ，发现 prefixMap 中有 10（根节点），计数 +1。 类似过程累计所有满足条件的路径。 复杂度分析 时间复杂度：O(N)，每个节点访问一次。 空间复杂度：O(N)，哈希表存储路径前缀和。