仅为个人记录复盘学习历程，解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
递归函数什么时候需要返回值？什么时候不需要返回值？
如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
如果要判断是否有符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。
112. 路径总和
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
提供参数：根结点root
关键思路：本题需要判断是否有符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。本题采用递归+回溯的方法来探索解空间树，使用先序遍历来遍历整个二叉树，在遍历过程中累计路径上的值，当遇到叶节点时进行判断累计值是否与目标值相等，进而判断本条路径是否满足条件，满足条件则返回，不满足条件继续遍历，直到满足条件或遍历完整棵树。本题在值的累加上使用相反的方法，遍历节点时减去当前节点的值。
主要操作：
递归三要素
1.返回值类型与参数：
本题需要返回值，且判断是否有满足条件的路径，返回值类型为boolean，参数为节点node，目标值count。
2.终止条件：
判断是否为叶子节点，且判断是否减去叶子节点的值后为0，为0返回true，否则为叶子节点返回false。
3.单层递归逻辑：
如果左子节点不为空，count减去当前结点值，继续遍历左子节点，结束后回溯（加回结点值）。
如果右子节点不为空，count减去当前结点值，继续遍历右子节点，结束后回溯（加回结点值）。
代码大致如下：
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null)return false;
return traversal(root,targetSum);
}
public boolean traversal(TreeNode node,int count){
//终止条件
if(node.left==null&&node.right==null&&count-node.val==0)return true;
if(node.left==null&&node.right==null)return false;
//单层递归逻辑
if(node.left!=null){
count-=node.val;
if(traversal(node.left,count))return true;
count+=node.val;
}
if(node.right!=null){
count-=node.val;
if(traversal(node.right,count))return true;
count+=node.val;
}
return false;
}113. 路径总和ii
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
提供参数：根结点root
关键思路：递归遍历+回溯，遍历是不仅仅需要记录累加值还需要记录路径信息，当遇到叶子节点时判断是否满足条件，满足条件将当前路径加入到结果集中，然后回溯，继续遍历，寻找所有满足条件的路径。
主要操作：
递归三要素
1.返回值类型和参数:
本题需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。需要参数节点node，和目标值计算count，需要全局变量res记录结果，path记录路径信息。
2.终止条件：
与上题终止条件类似，判断为叶子节点后，如果当前路径满足条件，则加入结果集，然后返回，如果不满足条件，则直接返回。
3.单层递归逻辑：
如果左子节点不为空，先将当前节点加入路径，减去当前节点值，遍历左子节点，完成后回溯（在路径中删除当前节点，加回当前结点值）。
如果右子节点不为空，先将当前节点加入路径，减去当前节点值，遍历右子节点，完成后回溯（在路径中删除当前节点，加回当前结点值）。
代码大致如下;
public List<List<Integer>>res;
public List<Integer>path;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res=new ArrayList<>();
path=new ArrayList<>();
if(root==null)return res;
traversal(root,targetSum);
return res;
}
public void traversal(TreeNode node,int count){
//终止条件
if(node.left==null&&node.right==null&&count-node.val==0){
path.add(node.val);
res.add(new ArrayList(path));
path.remove(path.size()-1);
return;
}
if(node.left==null&&node.right==null)return;
//单层递归逻辑
if(node.left!=null){
path.add(node.val);
count-=node.val;
traversal(node.left,count);
count+=node.val;
path.remove(path.size()-1);
}
if(node.right!=null){
path.add(node.val);
count-=node.val;
traversal(node.right,count);
count+=node.val;
path.remove(path.size()-1);
}
}