437. 路径总和 III

这是一道经典的 二叉树 + 前缀和（Prefix Sum） 问题，也可以用 双重递归 解决。题目要求统计所有向下路径（父 → 子方向）中，节点值之和等于 targetSum 的路径数目。

📌 关键点

• 路径 不必从根开始，也不必到叶子结束
• 但必须 自上而下连续（不能回头、不能跳跃）
• 节点值可为负数！（这点很重要，影响剪枝）

✅ 方法一：双重递归（直观易懂）

思路：

1. 对每个节点，以它为起点，向下搜索所有可能路径，看是否能凑出 targetSum
2. 递归遍历整棵树，对每个节点都做一次“路径和搜索”

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        
        // 以当前节点为起点的路径数 + 左子树中的路径数 + 右子树中的路径数
        return dfs(root, targetSum) 
             + pathSum(root.left, targetSum) 
             + pathSum(root.right, targetSum);
    }

    // 从 node 开始向下，找路径和等于 remain 的路径数
    private int dfs(TreeNode node, long remain) {
        if (node == null) return 0;
        
        int count = 0;
        if (node.val == remain) {
            count++; // 找到一条
        }
        
        // 继续向下（注意：即使找到，也要继续，因为可能有负数！）
        count += dfs(node.left, remain - node.val);
        count += dfs(node.right, remain - node.val);
        
        return count;
    }
}

⚠️ 注意使用 long 防止整数溢出（LeetCode 测试用例包含大数）

复杂度：

• 时间复杂度：O(n²) —— 每个节点作为起点遍历一次子树
• 空间复杂度：O(h)，h 为树高（递归栈）

适用于一般情况，代码清晰。

✅ 方法二：前缀和 + 哈希表（高效推荐）

🔍 核心思想（类比“和为 K 的子数组”）：

• 从根到当前节点的路径上，记录前缀和
• 若存在某个祖先节点的前缀和为 currSum - targetSum，则说明中间这段路径和为 targetSum
• 用 HashMap<前缀和, 出现次数> 快速查找

💡 Java 实现：

import java.util.*;

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0L, 1); // 初始化：前缀和为0出现1次（空路径）
        return dfs(root, 0L, targetSum, prefixSumCount);
    }

    private int dfs(TreeNode node, long currSum, int targetSum, Map<Long, Integer> prefixSumCount) {
        if (node == null) return 0;

        currSum += node.val;
        long need = currSum - targetSum;
        int count = prefixSumCount.getOrDefault(need, 0);

        // 将当前前缀和加入 map
        prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);

        // 递归左右子树
        count += dfs(node.left, currSum, targetSum, prefixSumCount);
        count += dfs(node.right, currSum, targetSum, prefixSumCount);

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

        return count;
    }
}

⏱️ 复杂度：

• 时间复杂度：O(n) —— 每个节点访问一次
• 空间复杂度：O(h) —— 哈希表最多存 h 个（树高），加上递归栈

✅ 这是最优解法，尤其适合大数据量

📌 总结对比