题目

题目来源：力扣（LeetCode）

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22，

  1.           5<br />             / \<br />            4   8<br />           /   / \<br />          11  13  4<br />         /  \    / \<br />        7    2  5   1<br />返回:

3
解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]

思路分析：

使用双层递归：

第一层：pathSum(root, sum)，路径是以根节点为起点，此时我们分别递归左子树和右子树，找到一个和为 sum 的路径数量

第二层：dfs(root, val)，路径不以根节点为起点，是有一个节点跟sum是相等的，当两者相等的时候，分别去递归左子树 和递归右子树。

因为整个递归是从上到下的dfs，所以不存在路径重复计算的问题

  1. /**
  2.  * @param {TreeNode} root
  3.  * @param {number} sum
  4.  * @return {number}
  5.  */
  6. // 用递归，判断当前根节点的值到底是选择还是不选择，如果从当前根节点的值选择的话，就如果不选择就证明我接下来递归左子树递归右子树找一个和为 22 的节点;以当前位置作为起点，找多少和值为22的路径数量;
  7. var pathSum = function (root, sum) {
  8.   // 找到从一个节点开始, 路径和为sum的所有路径
  9.   const dfs = (root, sum) => {
  10.     if (root == null) return 0;// 根节点为空，空树当中满足条件的路径数量为0；
  11.     let val = sum - root.val;// root.val == sum 证明找到一条路径
  12.     // (root.val == sum ? 1 : 0)
  13.     return (root.val == sum) + dfs(root.left,val)+ dfs(root.right,val)
  14.   };
  15.   if (root == null) return 0;
  16.   // 以root为起点查找和值为sum的路径数量，在左子树查找和值为sum的路径数量，在右子树查找和值为sum的路径数量
  17.   return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
  18. };