路径总和Ⅲ：递归

题目

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

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

思考

求和，想到什么？两数之和，梦开始的地方，接下来是前缀和，这个思想很重要，但是我总是忽略

代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // key: 前缀和, value: 该前缀和出现的次数
        Map<Long, Integer> prefixSumCount = new HashMap<>();

        // 基础情况：前缀和为 0 出现 1 次（用于处理从根节点开始的路径）
        prefixSumCount.put(0l, 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;
        }

        // 1. 计算当前节点的前缀和
        currSum += node.val;

        // 2. 查找是否有符合条件的前缀和 (currSum - targetSum)
        int res = prefixSumCount.getOrDefault(currSum - targetSum, 0);

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

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

        // 5. 回溯：离开当前节点时，将其前缀和的计数 -1，避免影响其他分支
        prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);

        return res;
    }
}

‍