递归
在一棵二叉树中寻找所有路径，每条路径节点值的和为目标值sum。假设根节点的值为val，由于二叉树的子树也是二叉树，问题可以转化为在左子树与右子树上寻找路径，该路径上的节点和为sum-val。所以可以使用二叉树的前序遍历的递归实现。
递归时添加路径上的节点，到达叶子节点时判断sum是否为0，如果为0则将这条路径保存。当递归返回父节点前删除路径上的当前节点。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private LinkedList<List<Integer>> ans = new LinkedList<>();//存放结果
private LinkedList<Integer> path = new LinkedList<>();//存放路径上的元素
public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null) {
return new LinkedList<>();
}
rcur(root, sum);
return ans;
}
private void rcur(TreeNode root, int sum){
sum -= root.val;
path.add(root.val);
//如果是叶子节点，判断sum是否为0
if(root.left == null && root.right == null){
if(sum == 0){
ans.add(new LinkedList(path));
}
}
//如果不是叶子节点就遍历其子节点，其子树中某条路径和为sum - root.val
if(root.left != null)
rcur(root.left, sum);
if(root.right!= null)
rcur(root.right, sum);
//返回父节点之前，删除路径上当前节点
path.removeLast();
}
}