sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

路径总和 III-437 #61

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二叉树不超过 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 题,递归的思路有点难找。

实际上这题需要统计三个值:

  1. 以 node 为起点,包含这个 node 本身加起来等于 sum 的路径数量之和。
  2. 以 node.left 为起点,等于 sum 的路径数量之和。
  3. 以 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 3 years ago

前缀和思路,和 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
};