///路径总和I
/*
1.确定递归函数的参数和返回类型
参数：需要二叉树的根节点，还需要一个计数器，这个计数器用来计算二叉树的一条边之和是否正好是目标和，计数器为int型。
*/
private boolean traversal(TreeNode root, int count){
if (root ==null){
return false;
}
/*
2.确定终止条件
首先计数器如何统计这一条路径的和呢？
不要去累加然后判断是否等于目标和，那么代码比较麻烦，可以用递减，让计数器count初始为目标和，然后每次减去遍历路径节点上的数值。
如果最后count == 0，同时到了叶子节点的话，说明找到了目标和。
如果遍历到了叶子节点，count不为0，就是没找到。
*/
if (root.left ==null && root.right ==null && count ==0){
return true;
}
if (root.left ==null && root.right ==null ){
return false;
}
/*
3.确定单层递归的逻辑
因为终止条件是判断叶子节点，所以递归的过程中就不要让空节点进入递归了。
如果未找到满足条件的，记得回溯
*/
if (root.left){
count -= root.left.val;
traversal(root.left, count); //递归
count += root.left.val; //不满足条件，回溯
}
if (root.right){
count -= root.right.val; //
traversal(root.right, count); //递归
count += root.right.val; //不满足条件，回溯
}
return false
}
/// 路径总和II
public List> pathsumII(TreeNode root, int count){
List> res =new ArrayList<>();
if (root ==null) {
return res;
}
List path =new ArrayList<>();
traversalII(root, count, res, path);
return res;
}
private void traversalII(TreeNode root, int count, List> result, List path){
path.add(root.val);
if (root.left ==null && root.right ==null && count ==0){
result.add(path);
return;
}
if (root.left){
count -= root.left.val; //count减去当前节点值
path.add(root.left.val); //添加当前值
traversal(root.left, count); //递归
count += root.left.val; //回溯
path.remove(path.size()-1);
}
if (root.right){
count -= root.right.val; //count进去当前节点值
path.add(root.right.val); //添加当前值
traversalII(root.right, count); //递归
count += root.right.val; //回溯
path.remove(path.size()-1);
}
}
