leetcode437-路径总和III

leetcode 437

思路

利用前缀和+hash map解答

前缀和在这里的含义是：从根节点到当前节点的路径上所有节点值的总和
我们使用一个 Map 数据结构来记录这些前缀和及其出现的次数
具体思路如下：

1. 初始化：创建一个 Map ，并将前缀和 0 出现的次数初始化为 1 。这是因为在遍历开始时，我们还没有访问任何节点，此时的前缀和就是 0 ，它的出现次数为 1 次。同时，初始化一个变量 count 用于记录满足条件的路径数量，初始值为 0

const map = new Map();​
map.set(0, 1);​
let count = 0;

2. 深度优先搜索：定义一个递归函数 deep 用于进行深度优先遍历。在每次递归中，我们计算当前节点的前缀和 curSum ，它等于从根节点到上一个节点的前缀和 sum 加上当前节点的值 root.val

const deep = (root, sum) => {​
if (!root) return;​
const curSum = sum + root.val;

3. 判断是否存在满足条件的路径：计算当前前缀和 curSum 与目标值 targetSum 的差值 diff ，即 diff = curSum - targetSum 。如果 Map 中存在 diff 这个前缀和，说明从根节点到当前节点的路径中，存在一段子路径的和等于目标值 targetSum ，那么满足条件的路径数量就需要加上 diff 出现的次数

const diff = curSum - targetSum​
if (map.has(diff)) {​count += map.get(diff);​
}

4. 更新前缀和及其出现次数：如果 Map 中已经存在当前前缀和 curSum ，则将其出现次数加 1 ；否则，将 curSum 加入 Map ，并将其出现次数设置为 1

if (map.has(curSum)) {​map.set(curSum, map.get(curSum) + 1)​
} else {​map.set(curSum, 1)​
}

5. 继续递归遍历左右子树：分别对当前节点的左子树和右子树进行递归调用，继续计算子树中的前缀和

root.left && deep(root.left, curSum)​
root.right && deep(root.right, curSum)

6. 回溯：在递归返回时，需要进行回溯操作。因为我们已经遍历完当前节点的子树，要回到上一层节点继续遍历，所以需要将当前前缀和 curSum 的出现次数减 1 ，以保证 Map 中记录的前缀和状态只反映从根节点到当前层节点的情况

map.set(curSum, map.get(curSum) - 1)

难点-使用回溯

在本题实现的过程中，可能会忽略掉回溯的步骤

那么为什么需要回溯操作

模拟实现：考虑如下二叉树（目标和 targetSum = -1）：

    1/ \-2  -3

若无回溯：

1. 遍历根节点 1
   • 前缀和 curSum = 1，差值 1 - (-1) = 2，map 中无 2，不计数
   • map 状态：{0:1, 1:1}
   • 递归左子树 -2
2. 遍历左子节点 -2
   • 前缀和 curSum = 1 + (-2) = -1，差值 -1 - (-1) = 0，map 中存在 0（初始值），计数 + 1（路径[1, -2]正确）。
   • 未回溯时，map 状态：{0:1, 1:1, -1:1}（保留 -1 的计数）。
   • 左、右子树为空，返回根节点
3. 递归右子树 -3
   • 前缀和 curSum = 1 + (-3) = -2，差值 -2 - (-1) = -1
   • 此时 map 中存在 -1（来自左子树的记录），算法错误认为存在路径和为 -1，计数 + 1
   • 错误结果：count = 2，但实际仅[1, -2]满足条件

其实在这里第三步中diff = -1此时map中不应该存在-1这一项，因为这里的map只是1->-3 ，却把1->2的部分也存储了起来，导致结果的不准确，使得1->2这条路径重复计算，结果出错

回溯的作用（有回溯时）

• 离开左子节点 -2 时，执行 map.set(-1, 0)，map 恢复为 {0:1, 1:1}。
• 遍历右子树 -3 时，前缀和 -2 的差值 -1 在 map 中无匹配，不计数。
• 正确结果：count = 1

实现

var pathSum = function (root, targetSum) {const map = new Map();map.set(0, 1);let count = 0; // 满足条件的路径const deep = (root, sum) => {if (!root) return;const curSum = sum + root.val;const diff = curSum - targetSumif (map.has(diff)) {count += map.get(diff);}if (map.has(curSum)) {map.set(curSum, map.get(curSum) + 1)} else {map.set(curSum, 1)}// 左root.left && deep(root.left, curSum)// 右root.right && deep(root.right, curSum)// 回溯map.set(curSum, map.get(curSum) - 1)}deep(root, 0)return count;
};