🔗 路径总和 III

题目来源：437. 路径总和 III – 力扣（LeetCode）

---

📌 题目描述

给定一个二叉树的根节点 root 和一个整数 targetSum，求该二叉树中节点值之和等于 targetSum 的路径数目。

路径要求：

• 不需要从根节点开始；
• 不需要在叶子节点结束；
• 方向必须是向下的（只能从父节点到子节点）。

---

✅ 示例解析

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

解释：
和为 8 的路径有 3 条：

• 5 → 3
• 5 → 2 → 1
• -3 → 11

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

---

⚠️ 提示

• 节点个数范围：[0, 1000]
• Node.val 范围：[-10⁹, 10⁹]
• targetSum 范围：[-1000, 1000]

⚠️ 注意：节点值可能为负数，因此不能提前剪枝！

---

💡 解法：前缀和 + 哈希表 + DFS —— O(n) 时间，O(h) 空间

class Solution {
    int targetSum;
    Map<Long, Integer> prefixSumCount = new HashMap<>();
    int result = 0;

    public int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        // 初始化：前缀和为 0 的路径有 1 条（空路径）
        prefixSumCount.put(0L, 1);
        dfs(root, 0L);
        return result;
    }

    private void dfs(TreeNode node, long currentSum) {
        if (node == null) return;

        // 更新当前路径前缀和
        currentSum += node.val;

        // 检查是否存在前缀和 = currentSum - targetSum
        long need = currentSum - targetSum;
        if (prefixSumCount.containsKey(need)) {
            result += prefixSumCount.get(need);
        }

        // 将当前前缀和加入哈希表
        prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);

        // 递归左右子树
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);

        // 回溯：移除当前前缀和（避免影响其他路径）
        prefixSumCount.put(currentSum, prefixSumCount.get(currentSum) - 1);
    }
}

✅ 关键点：

• 使用 前缀和思想：若 sum[A→C] - sum[A→B] = targetSum，则 sum[B→C] = targetSum；
• 用 哈希表记录从根到当前节点路径上所有前缀和的出现次数；
• 回溯时删除当前前缀和，确保只统计当前 DFS 路径上的前缀和。

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个节点访问一次，哈希表操作 O(1)。
• 空间复杂度：O(h)
  • 哈希表最多存储 h 个前缀和（h 为树高）；
  • 递归栈深度为 O(h)；
  • 最坏情况（链表）：h = n → O(n)；
  • 最好情况（平衡树）：h = log n → O(log n)。

---

🧩 解题思路

为什么不能用暴力 DFS？

暴力做法：对每个节点，向下遍历所有路径求和。

• 时间复杂度：O(n²)（每个节点作为起点遍历一次）
• 在 n = 1000 时勉强通过，但不够优雅，且无法应对更大规模。

前缀和的核心思想

类比数组中的“和为 K 的子数组”问题（LeetCode 560）

在一条从根到叶的路径上，路径和具有连续性。
设从根到当前节点的路径和为 S，若之前某处前缀和为 S - targetSum，
则这两点之间的路径和正好为 targetSum。

例如：

• 路径：10 → 5 → 3，前缀和依次为 10, 15, 18
• targetSum = 8，当前 S = 18，需要找 18 - 8 = 10
• 发现前缀和 10 出现过 1 次 → 找到一条路径：5 → 3

为什么需要回溯？

因为哈希表记录的是当前 DFS 路径上的前缀和。
当从左子树返回时，必须移除左子树产生的前缀和，否则会错误地影响右子树的统计。

🌰 举例：
根为 10，左子树路径产生前缀和 15，若不回溯，
右子树会误以为 15 是从根到右子树某点的前缀和，导致错误计数。