算法1

(前序遍历，递归) $O(n)$

本题很容易可以想到是前序遍历，因为要从根节点往下加数，要先加上自己，然后再加上自己的子树，所以用前序遍历即可。

难点在于如何从子树回到父节点，书上的方法是用一个栈，本题的要求是一个链表，则删除链表的最后一个节点即可，然后不断的new一个子链表，将其加入最后的链表即可。

Java 代码

class Solution {
    public List<List<Integer>> findPath(TreeNode root, int target) {
        List<List<Integer>> arr = new ArrayList<>();
        if(root == null)
            return arr;
        int  sum = 0;
        List<Integer> arr1 = new ArrayList<>();
        pa(root, target, arr, arr1,sum);
        return arr;
    }
    public void pa(TreeNode root,int target,List<List<Integer>> arr, List<Integer> a1,int sum){
        if(root==null)
            return;

        sum += root.val;

        if(root.left==null&&root.right==null){
            if(sum==target){
                a1.add(root.val);
                arr.add(new ArrayList<Integer>(a1));
                a1.remove(a1.size()-1);
            }
            return;
        }

        a1.add(root.val);
        pa(root.left, target, arr, a1,sum);
        pa(root.right, target, arr, a1,sum);
        a1.remove(a1.size()-1);
        return ;
    } 
}