437. 路径总和 III
题目
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
解题思路
这题采用双递归的方式，但是依旧是按照递归的模板来（1.找到最简单的子问题求解，2.其他问题不考虑内在细节，只考虑整体逻辑）。
题目要求 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点） 。这就要求我们只需要去求三部分即可：
- 以当前节点作为头结点的路径数量
- 以当前节点的左孩子作为头结点的路径数量
- 以当前节点的右孩子作为头结点啊路径数量
将这三部分之和作为最后结果即可。
但是注意我们要新写一个辅助方法，用来求上面三种情况的路径，并且在这个辅助函数里面还要递归调用。
即：假如现在传了一个root给辅助函数，因为“不需要在叶子节点结束”，所以每隔一个节点都要判断一次这一个节点的值满不满足要求，也就是sum-root.val是否为0.如果是结果路径+1，然后 “不管上一步的路径是否加1”我们都要去找root的左子树 ，右子树，即“找到一个节点要做的事，剩下的交给递归框架”
代码
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
int result = countPath(root,sum);
int a = pathSum(root.left,sum);
int b = pathSum(root.right,sum);
return result+a+b;
}
public int countPath(TreeNode root,int sum){
if(root == null){
return 0;
}
sum = sum - root.val;//用sum减去root.val看是不是0；
int result = sum == 0 ? 1:0;//如果是0，证明满足条件，路径为1
int leftCount=countPath(root.left,sum);
int rightCount=countPath(root.right,sum);
return result + leftCount + rightCount;
}
}
