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

本文主要是介绍【前缀和】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 数量是1return 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;// 左右子树的结果 加到resmap.put(curSum,map.get(curSum) - 1);// 回溯 减少出现次数return res;}
}