题目
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
摘自LeetCode112
解题方法
递归实现
目标sum值减去根节点的关键值，结果分别是根节点的左右子树的目标和。对左右子树递归调用函数，直到树叶节点为止。
代码
public boolean hasPathSum(TreeNode root, int sum) {
if(null == root){//根节点为空，则返回false
return false;
}
//直到树叶节点，如果关键值等于递归传入的sum值，则返回true
if(null == root.left && null == root.right && root.val == sum){
return true;
}
//非树叶节点，对左右子树递归调用函数
//目标和要减去当前节点的关键值
boolean l = hasPathSum(root.left, sum - root.val);
boolean r = hasPathSum(root.right, sum - root.val);
return l || r;
}
拓展题目
如果题目要求不是判断是否存在这条路径，而是返回满足条件的路径？（LeetCode113）
拓展题目解析
- 与上一题思路一样，区别在于递归不再返回是否存在路径，而是需要记录遍历过的节点。
- 实现中我们在递归函数中传入用于存储遍历过节点的队列结构。
- 同时，因为递归是先遍历左子树再遍历右子树，只有左子树递归到树叶节点之后才会开始遍历右子树，那么我们可以仅仅使用同一个队列进行参数传递，在每个节点的左右子树递归遍历之后，移除当前的节点，这样可以减少不断构建新队列所带来的性能消耗。
拓展题目代码
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> list = new ArrayList<>();
pathSumHelper(root, sum, result, list);
return result;
}
//递归寻找存在的路径
private void pathSumHelper(TreeNode root, int sum,
List<List<Integer>> result, List<Integer> list){
if(null == root){
return;
}
if(null == root.left && null == root.right && sum == root.val){
//遍历到树叶节点如果符合条件，存入队列中
list.add(root.val);
//复制一个新的队列存入结果队列中
result.add(new ArrayList<Integer>(list));
//移除当前节点，其他遍历分支继续使用这个队列
list.remove(list.size() - 1);
return;
}
//遍历到非树叶节点，存入队列中
list.add(root.val);
//递归左子树与右子树
pathSumHelper(root.left, sum - root.val, result, list);
pathSumHelper(root.right, sum - root.val, result, list);
//移除当前节点，其他遍历分支继续使用这个队列
list.remove(list.size() - 1);
}
