如果需要遍历搜索整棵树，那么递归函数就不需要返回值
如果需要搜索其中一条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径就要及时返回
一、Java 求解路径总和
1. 题目
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点是指没有子节点的节点。
2. 题目分析
题目要求遍历从根节点到叶子节点的路径总和是否等于目标值
也就是类似找二叉树的路径，判断是否符合条件，符合条件就终止遍历
对于相加总和是否满足目标值，相加比较麻烦，可以采用递减思路，目标值减到0表示满足条件
具体实现，可参考代码
3. 递归法
（1）确定递归函数的参数和返回类型
递归函数的参数就是二叉树节点，返回类型为 boolean
因为没必要遍历所有的路径，找到一个符合条件的路径就可以终止，所以需要返回值，如果需要遍历树所有的路径，则不需要返回值
图中可以看出，遍历的路线，并不要遍历整棵树，所以递归函数需要返回值，可以用 bool 类型表示。
（2）确定递归终止条件
到达叶子节点同时满足条件或者到达叶子节点但是没有满足条件
对于找路径，到达叶子节点即该路径遍历结束
if(count==0 && root.left==null && root.right==null){}
if(root.left==null && root.right==null){}
（3）确定单层遍历逻辑
由于递归终止条件是叶子节点，所以不能让空节点进入递归
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
return travlePath(root, targetSum - root.val);
}
public boolean travlePath(TreeNode root, int count) {
//递归到叶子节点，且相加和为targetSum
if (count == 0 && root.left == null && root.right == null) {
return true;
}
//不符合条件
if (root.left == null && root.right == null) {
return false;
}
if (root.left != null) {
//递归中隐藏着回溯：count - root.left.val
if (travlePath(root.left, count - root.left.val)) {
return true;
}
}
if (root.right != null) {
//递归中隐藏着回溯：count - root.left.val
if (travlePath(root.right, count - root.right.val)) {
return true;
}
}
return false;
}
}
精简版：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
//需要算上叶子节点，所以需要把叶子节点的值减去
if(targetSum==root.val && root.left==null && root.right==null){
return true;
}
return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
}
}
二、Java 求解路径总和 II
1. 题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
2. 递归法
题目分析同第一题，这里只是需要遍历所有的路径，记录满足条件的路径
class Solution {
List<List<Integer>> lists = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return lists;
}
deque.addFirst(root.val);
travelPath(root, targetSum - root.val);
return lists;
}
public void travelPath(TreeNode root, int count) {
if (count == 0 && root.left == null && root.right == null) {
lists.add(new ArrayList(deque));
return;
}
if (root.left == null && root.right == null) {
return;
}
if (root.left != null) {
deque.add(root.left.val);
travelPath(root.left, count - root.left.val);
deque.removeLast();
}
if (root.right != null) {
deque.add(root.right.val);
travelPath(root.right, count - root.right.val);
deque.removeLast();
}
return;
}
}
注意只能采用队列记录，结果有顺序要求，如果采用栈记录则顺序不符合要求
三、总结
对于求解二叉树路径的题目，注意递归终止条件是到达叶子节点：
if(root.left==null && root.right==null){}
对于递归函数是否需要返回值，需要根据是否需要遍历所有的路径来决定，如果需要遍历所有的路径，则不需要返回值，如果是找其中满足条件的一个路径即可，则需要返回值
在递归函数有返回值的情况下： 如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）