437. 路径总和 III#

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 边界处理：空树中不存在任何路径
        if (root == null) return 0;

        // 总路径数 =
        // 1) 以当前节点为起点的合法路径数
        // 2) 左子树内部的合法路径数
        // 3) 右子树内部的合法路径数
        return countPath(root, targetSum) 
             + pathSum(root.left, targetSum) 
             + pathSum(root.right, targetSum);
    }

    private int countPath(TreeNode node, long targetSum) {
        // 递归终止：空节点不产生路径
        if (node == null) return 0;

        // 记录“以当前节点为起点”时，满足条件的路径数量
        int count = 0;
        // 如果当前节点值刚好等于剩余目标值，则找到一条路径
        if (node.val == targetSum) {
            count++;
        }

        // 继续向左搜索，新的目标值要减去当前节点值
        count += countPath(node.left, targetSum - node.val);
        // 继续向右搜索，新的目标值同样减去当前节点值
        count += countPath(node.right, targetSum - node.val);
        // 返回从当前节点出发可形成的路径总数
        return count;
    }
}

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 前缀和哈希表：key=前缀和，value=该前缀和出现次数
        Map<Long, Integer> prefixSumMap = new HashMap<>();
        // 初始化：前缀和为 0 出现 1 次（表示“从根之前开始”）
        prefixSumMap.put(0L, 1); // 初始化
        // 从根节点开始 DFS，currentSum 初始为 0
        return dfs(root, 0L, targetSum, prefixSumMap);
    }

    private int dfs(TreeNode node, long currentSum, int targetSum, Map<Long, Integer> prefixSumMap) {
        // 递归终止：空节点贡献路径数为 0
        if (node == null) return 0;

        // 将当前节点值加入路径和，得到“根到当前节点”的前缀和
        currentSum += node.val; // 更新当前路径和
        // 若存在某个历史前缀和 = currentSum - targetSum，
        // 则“历史节点之后到当前节点”这段路径和恰好为 targetSum
        int count = prefixSumMap.getOrDefault(currentSum - targetSum, 0); // 查找满足条件的路径

        // 将当前前缀和计入哈希表，供子树节点使用
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);

        // 递归统计左子树中的合法路径
        count += dfs(node.left, currentSum, targetSum, prefixSumMap);
        // 递归统计右子树中的合法路径
        count += dfs(node.right, currentSum, targetSum, prefixSumMap);

        // 回溯：离开当前节点前，撤销当前前缀和出现次数
        // 避免影响兄弟分支的统计结果
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);
        // 返回以当前节点为根的子树中路径总数
        return count;
    }
}