响应式网站缺点,品牌红酒的网站建设,内网门户网站建设方案,wordpress登录按钮leetcode 437
思路
利用前缀和hash map解答
前缀和在这里的含义是#xff1a;从根节点到当前节点的路径上所有节点值的总和 我们使用一个 Map 数据结构来记录这些前缀和及其出现的次数 具体思路如下#xff1a;
初始化#xff1a;创建一个 Map #xff0c;并将前缀和 …leetcode 437
思路
利用前缀和hash map解答
前缀和在这里的含义是从根节点到当前节点的路径上所有节点值的总和 我们使用一个 Map 数据结构来记录这些前缀和及其出现的次数 具体思路如下
初始化创建一个 Map 并将前缀和 0 出现的次数初始化为 1 。这是因为在遍历开始时我们还没有访问任何节点此时的前缀和就是 0 它的出现次数为 1 次。同时初始化一个变量 count 用于记录满足条件的路径数量初始值为 0
const map new Map();
map.set(0, 1);
let count 0;深度优先搜索定义一个递归函数 deep 用于进行深度优先遍历。在每次递归中我们计算当前节点的前缀和 curSum 它等于从根节点到上一个节点的前缀和 sum 加上当前节点的值 root.val
const deep (root, sum) {
if (!root) return;
const curSum sum root.val;判断是否存在满足条件的路径计算当前前缀和 curSum 与目标值 targetSum 的差值 diff 即 diff curSum - targetSum 。如果 Map 中存在 diff 这个前缀和说明从根节点到当前节点的路径中存在一段子路径的和等于目标值 targetSum 那么满足条件的路径数量就需要加上 diff 出现的次数
const diff curSum - targetSum
if (map.has(diff)) {count map.get(diff);
}更新前缀和及其出现次数如果 Map 中已经存在当前前缀和 curSum 则将其出现次数加 1 否则将 curSum 加入 Map 并将其出现次数设置为 1
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)回溯在递归返回时需要进行回溯操作。因为我们已经遍历完当前节点的子树要回到上一层节点继续遍历所以需要将当前前缀和 curSum 的出现次数减 1 以保证 Map 中记录的前缀和状态只反映从根节点到当前层节点的情况
map.set(curSum, map.get(curSum) - 1)难点-使用回溯
在本题实现的过程中可能会忽略掉回溯的步骤
那么为什么需要回溯操作
模拟实现考虑如下二叉树目标和 targetSum -1 1/ \-2 -3若无回溯
遍历根节点 1 前缀和 curSum 1差值 1 - (-1) 2map 中无 2不计数map 状态{0:1, 1:1}递归左子树 -2 遍历左子节点 -2 前缀和 curSum 1 (-2) -1差值 -1 - (-1) 0map 中存在 0初始值计数 1路径[1, -2]正确。未回溯时map 状态{0:1, 1:1, -1:1}保留 -1 的计数。左、右子树为空返回根节点 递归右子树 -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;
};
