Path Sum

LC437. Path Sum III

给一棵二叉树，和一个目标值，节点上的值有正有负，返回树中和等于目标值的路径条数，路径必须是downward的。

分析：首先明确，递归求解树的问题必然是要遍历整棵树的，所以 二叉树的遍历框架 （分别对左右孩子递归调用函数本身）必然要出现在主函数 pathSum 中。那么对于每个节点，它们应该干什么呢？它们应该看看，自己和脚底下的小弟们包含多少条符合条件的路径。好了，这道题就结束了。

按照前面说的技巧，根据刚才的分析来定义清楚每个递归函数应该做的事：

PathSum 函数：给它一个节点和一个目标值，它返回以这个节点为根的树中，和为目标值的路径总数。

count 函数：给它一个节点和一个目标值，它返回以这个节点为根的树中，能凑出几个以该节点为路径开头，和为目标值的路径总数。

/* 有了以上铺垫，详细注释一下代码 */
int pathSum(TreeNode root, int sum) {
  if (root == null) return 0;
  int pathImLeading = count(root, sum);  // 自己为开头的路径数
  int leftPathSum = pathSum(root.left, sum);  // 左边路径总数（相信他能算出来）
  int rightPathSum =
      pathSum(root.right, sum);  // 右边路径总数（相信他能算出来）
  return leftPathSum + rightPathSum + pathImLeading;
}
int count(TreeNode node, int sum) {
  if (node == null) return 0;
  // 我自己能不能独当一面，作为一条单独的路径呢？
  int isMe = (node.val == sum) ? 1 : 0;
  // 左边的小老弟，你那边能凑几个 sum - node.val 呀？
  int leftBrother = count(node.left, sum - node.val);
  // 右边的小老弟，你那边能凑几个 sum - node.val 呀？
  int rightBrother = count(node.right, sum - node.val);
  return isMe + leftBrother + rightBrother;  // 我这能凑这么多个
}

 写递归的技巧：

 明白一个函数的作用并相信它能完成这个任务，千万不要试图跳进细节。 千万不要跳进这个函数里面企图探究更多细节，否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。