Leetcode 路径总和 III

java 解法一：双递归

class Solution {
    public int pathSum(TreeNode root, long targetSum) { //外层递归,把每个节点都当作路径起点
        if(root == null) return 0;
        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode node, long targetSum) { //内层递归,
    //从当前节点往下探索路径，看是否存在一条或多条路径满足 路径和为 targetSum
        if(node == null) return 0;

        int ret = 0;
        if(node.val == targetSum) {
            ret++;
        }
        ret += rootSum(node.left, targetSum - node.val);
        ret += rootSum(node.right, targetSum - node.val);
        return ret;
    }
}

解法二：前缀和 + 回溯

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // 首先创建一个hashmap
        // key: 前缀和, value: 该前缀和出现的次数
        Map<Long, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0L, 1); //初始化前缀和为0的路径数量
        return dfs(root, 0L, targetSum, prefixSumCount);
    }

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

        curSum += node.val; //更新curSum
        //先查找有多少前缀和满足 curSum - targetSum
        int count = prefixSumCount.getOrDefault(curSum - targetSum, 0);

        //然后更新prefixSumCount
        prefixSumCount.put(curSum, prefixSumCount.getOrDefault(curSum, 0) + 1);

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

        //回溯撤销
        prefixSumCount.put(curSum, prefixSumCount.get(curSum) - 1);

        return count;
    }
}