路径总和 III-437
sl1673495 opened this issue · 1 comments
sl1673495 commented
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过 1000 个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/path-sum-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这是一道被吐槽难度的 easy 题,递归的思路有点难找。
实际上这题需要统计三个值:
- 以 node 为起点,包含这个 node 本身加起来等于 sum 的路径数量之和。
- 以 node.left 为起点,等于 sum 的路径数量之和。
- 以 node.right 为起点,等于 sum 的路径数量之和。
let pathSum = function (root, sum) {
if (!root) return 0
return (
countSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
)
}
let countSum = (node, sum) => {
let count = 0
let dfs = (node, target) => {
if (!node) return
// 这里拿到结果不能直接return 要继续向下考虑
// 比如下面的两个节点是 1, -1 那么它们相加得 0 也能得到一个路径
if (node.val === target) {
count += 1
}
dfs(node.left, target - node.val)
dfs(node.right, target - node.val)
}
dfs(node, sum)
return count
}
vortesnail commented
前缀和思路,和 560. 和为K的子数组 这道题思路一致,只不过对于后者是迭代,在二叉树中是递归而已,另外还要考虑回溯。
关于前缀和,这个题解说的特别清楚特别好:前缀和的运用,一步步优化,希望能帮到还困惑于此且看到这里的有缘人。
var pathSum = function (root, targetSum) {
const map = Object.create(null);
map[0] = 1;
let res = 0;
var dfs = function (root, prefixSum) {
if (!root) return 0;
let sum = prefixSum + root.val;
if (map[sum - targetSum] > 0) {
res += map[sum - targetSum];
}
if (map[sum] > 0) {
map[sum]++;
} else {
map[sum] = 1;
}
dfs(root.left, sum)
dfs(root.right, sum)
map[sum]--;
}
dfs(root, 0);
return res
};