437. 路径总和 III
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
- 5 -> 3
- 5 -> 2 -> 1
- -3 -> 11
双重递归
/*
思路：
1.dfs是求从根节点出发到叶子节点满足条件的路径总数
2.将给定的二叉树看成三个部分：根节点、左子树、右子树
3.三部分可以看成一个递归结构，先求从根节点出发满足条件的路径总数(dfs(root))，
再递归求左子树(pathSum(root.left))，递归求右子树(pathSum(root.right))
总结：
1.双重递归，从全局找外层递归(如思路中的三个部分)，再从部分中找内层递归(如思路中的dfs)
*/
class Solution {
private int count = 0; //存放结果
public int pathSum(TreeNode root, int sum) {
if(root == null) return 0;
dfs(root, sum); //求从根节点出发满足条件的路径总数
pathSum(root.left, sum); //递归求左子树
pathSum(root.right, sum); //递归求右子树
return count;
}
private void dfs(TreeNode root, int sum){
if(root == null) return;
sum -= root.val;
if(sum == 0) count++; //满足条件结果加一
dfs(root.left, sum); //继续往左子树找
dfs(root.right, sum); //继续往右子树找
}
}
单重递归
/*
思路：
1.用双重递归会重复计算很多次，其实我们只用单递归就可以解决，
不妨将已经走过的路径值保存到book数组
2.到i节点，就可以根据book倒序遍历，找到从i节点到根节点满足条件的路径总数
3.递归到最底层也就是叶子节点时，找出叶子节点到根节点的满足条件的路径总数之后，
需要将book数组回溯到上一层的状态，以便从上一层继续寻找
总结：
1.将已经求出的值保存，当下次递归时可以直接使用，
省去了重复计算浪费的时间，相当于用空间换取时间
2.递归返回到上层时，我们有时需要原来上层递归的状态，这时就需要用到回溯
*/
class Solution {
private int count = 0; //存放结果
public int pathSum(TreeNode root, int sum) {
dfs(root, sum, new ArrayList<Integer>());
return count;
}
private void dfs(TreeNode root, int sum, ArrayList<Integer> book){
if(root == null) return;
book.add(root.val); //加入当前节点的值
int cur_sum = 0;
for(int i = book.size() - 1; i >= 0; i--){ //从当前节点往根节点寻找满足条件的路径总数
cur_sum += book.get(i);
if(cur_sum == sum) count++;
}
dfs(root.left, sum, book); //递归求左子树
dfs(root.right, sum, book); //递归求右子树
book.remove(book.size() - 1); //回溯到上一次的状态，以便继续寻找
}
}
