【前缀和】437. 路径总和 III

437. 路径总和 III

解题思路

• 递归遍历二叉树： 使用深度优先搜索（DFS）的方式遍历二叉树。对于每个节点，计算包含该节点的路径的前缀和。

• 使用哈希映射记录前缀和： 哈希映射 prefixMap 用于记录当前路径的前缀和及其出现的次数。这样可以在遍历过程中快速查找是否存在路径和为目标值的子路径。

• 路径和的计算： 在递归过程中，对于当前节点，更新当前路径的前缀和，并通过哈希映射查找是否存在前缀和为 (curSum - target) 的路径。累加这个数量到结果中。

• 递归回溯： 在递归的过程中，要注意回溯操作。在处理完当前节点后，需要将当前前缀和在 prefixMap 中的出现次数减去，以便在父节点处继续使用正确的前缀和信息。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Long,Integer> map;// Key是代表前缀和  value代表前缀和出现的次数
    int target;// 目标和

    public int pathSum(TreeNode root, int targetSum) {
        // 两节点间的路径和 = 两节点的前缀和之差

        // 遍历整棵树  记录每一个节点的前缀和 然后查询该节点祖先节点中符合条件的个数 将数量加到最后结果上面
        map = new HashMap<>();
        target = targetSum;// 目标和
        map.put(0L,1);// 根节点的前缀和是0 数量是1
        return traverse(root,0L);
    }

    // curSum 代表之前的前缀和
    private int traverse(TreeNode node,Long curSum){
        if(node == null){
            return 0;
        }

        int res = 0;
        curSum += node.val;// 添加当前节点的值  计算当前路径的前缀和

        // curSum -target 表示前缀和 res 添加 当前前缀和的次数
        res += map.getOrDefault(curSum - target,0);

        // 更新当前前缀和的出现次数
        map.put(curSum,map.getOrDefault(curSum,0) + 1);

        // 递归左右子树 分别传递左右子节点和更新之后的前缀和
        int left = traverse(node.left,curSum);
        int right = traverse(node.right,curSum);

        res =  res + left + right;// 左右子树的结果 加到res
        map.put(curSum,map.get(curSum) - 1);// 回溯 减少出现次数

        return res;
    }
}