给你二叉树的根节点
root和一个整数目标和targetSum，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
在这里给大家提供两种方法进行思考，第一种方法是递归，第二种方式使用回溯的方式进行爆搜
递归：树具有天然的递归结构，将一个大的问题转换成多个相同的子问题而进行解决，就相当于你会0-1的算式，你自然而然可以推导出0-n的算式（递归终止条件+递归操作）
我觉的这个图可以很形象的说明一些问题，通过改变每个结点的差值，最后进行叶子结点与传入的target进行比较，如果相等，就说明树中肯定有满足情况的路径
解题步骤：
- 方法中返回什么，我们就创建什么
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> resList=new LinkedList<>();
...
}- 递归结束的条件（分为第一次入参和叶子结点的入参，两者的操作不一样）
//如果传进行的叶子结点为空，直接返回一个空链表
if(root==null){
return resList;
}
//如果是叶子结点且叶子结点的值等于target,则该叶子结点是满足情况下的一条路径上的值
if(root.left==null&&root.right==null){
if(root.val==targetSum){
List<Integer> list=new LinkedList<>();
list.add(root.val);
//将该路径加入总结果集中
resList.add(list);
}
return resList;
}- 每次递归的时候将target-root.val作为参数传下去
int diff=targetSum-root.val;- 如果左树不为空，递归左树，如果右树不为空，递归右树
if(root.left!=null){
List<List<Integer>> curList=pathSum(root.left,diff);
for(int i=0;i<curList.size();i++){
List<Integer> list1=curList.get(i);
//将该节点加入路径中
list1.add(0,root.val);
//加入到结果集中
resList.add(list1);
}
}
if(root.right!=null){
List<List<Integer>> curList=pathSum(root.right,diff);
for(int i=0;i<curList.size();i++){
List<Integer> list1=curList.get(i);
list1.add(0,root.val);
resList.add(list1);
}
}- 最后每次递归结束后返回结果集，供归的时候进行使用
return resList;方法二：回溯
回溯的方法相当于暴力搜索一样，但是对于面试而言，我更加推荐回溯（比较容易记忆）
//大体思想其实和递归差不多，就是回溯这种题有个特定的模板，有的时候，即使你不会做，那你也有可能把题做出来
List<List<Integer>> resList=new LinkedList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root==null){
return resList;
}
backtracing(root,targetSum);
return resList;
}
public void backtracing(TreeNode root,int targetSum){
if(root==null){
return;
}
path.add(root.val);
if(targetSum==root.val&&root.left==null&&root.right==null){
resList.add(new ArrayList<>(path));
}
int diff=targetSum-root.val;
if(root.left!=null){
pathSum(root.left,diff);
//回溯
path.remove(path.size()-1);}
if(root.right!=null){
pathSum(root.right,diff);
path.remove(path.size()-1);
}
}
