437.路径总和 III

路径总和 III

给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的。

解析

前缀和 + 回溯。

var pathSum = function (root, targetSum) {
  let count = 0;
  const prefixMap = new Map([[0, 1]]);
  function dfs(node, currSum) {
    if (!node) return;
    currSum += node.val;
    count += prefixMap.get(currSum - targetSum) || 0;
    prefixMap.set(currSum, (prefixMap.get(currSum) || 0) + 1);
    dfs(node.left, currSum);
    dfs(node.right, currSum);
    prefixMap.set(currSum, prefixMap.get(currSum) - 1);
  }
  dfs(root, 0);
  return count;
};