路径总和 III

题目描述：

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

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

示例 1： 

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

 示例 2：

输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出： 3

解题思路 

思路一： 深度优先搜索

穷举所有的可能，我们访问每一个节点 node，检测以 node 为起始节点且向下延深的路径有多少种。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果

• 定义 rootSum(p, sum) 表示以节点 p 为起点向下且满足路径总和为 sum 的路径数目。我们对二叉树上每个节点 p 求出 rootSum(p,targetSum)，然后对这些路径数目求和即为返回结果。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
  if (root == null) {
    return 0;
  }
  let result = rootSum(root, targetSum);
  result += pathSum(root.left, targetSum);
  result += pathSum(root.right, targetSum);
  return result;
};

var rootSum = function (node, sum) {
  if (node == null) {
    return 0;
  }
  let result = 0, val = node.val;
  if (val == sum) {
    result++;
  }
  // 对左子树和右子树进行递归搜索
  result += rootSum(node.left, sum - val);
  result += rootSum(node.right, sum - val);
  return result;
}

时间复杂度： O(N^2)，其中 n 是二叉树中的节点个数

对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(N^2)。

空间复杂度： O(N)

思路二： 前缀和

解法一中应该存在许多重复计算，我们可以利用前缀和进行优化。 前缀和为：由根结点到当前结点的路径上所有节点的和。我们利用先序遍历二叉树，记录下根节点 root 到当前节点 p 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 currcurr 减去 targetSum。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
  // key是前缀和, value是大小为key的前缀和出现的次数
  const prefix = new Map();
  // 前缀和为0的一条路径
  prefix.set(0, 1);
  return dfs(root, prefix, 0, targetSum);
};

/**
 * 前缀和的递归回溯思路
 * 从当前节点反推到根节点(反推比较好理解，正向其实也只有一条)，有且仅有一条路径，因为这是一棵树
 * 如果此前有和为curr - targetSum, 而当前的和又为curr, 两者的差就肯定为targetSum了
 * 所以前缀和对于当前路径来说是唯一的，当前记录的前缀和，在回溯结束，回到本层时去除，保证其不影响其他分支的结果
 * @param {*} root 树节点
 * @param {*} prefix 前缀和Map
 * @param {*} curr 当前路径和
 * @param {*} targetSum 目标值
 * 
 */
const dfs = (root, prefix, curr, targetSum) => {
  // 递归终止条件
  if (root == null) {
      return 0;
  }

  let ret = 0;
  // 当前路径上的和
  curr += root.val;

  ret = prefix.get(curr - targetSum) || 0;
  prefix.set(curr, (prefix.get(curr) || 0) + 1);
  ret += dfs(root.left, prefix, curr, targetSum);
  ret += dfs(root.right, prefix, curr, targetSum);
  prefix.set(curr, (prefix.get(curr) || 0) - 1);

  return ret;
}

时间复杂度：O(N)，其中 N 为二叉树中节点的个数。利用前缀和只需遍历一次二叉树即可。

空间复杂度：O(N)

参考资料

437. 路径总和 III - 力扣（LeetCode） (leetcode-cn.com)