这里要注意空间复杂度，回溯的时候要从路径集合中去掉最后加入的点。值得细品。
    image.png
    我的代码效率不是很高
    https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/solution/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-68dg/
    主要在temp列表进行赋值的时候，好的方法是用回溯，我这个是每一次都开辟两个空间，

    1.  public static void main(String[] args) {
    2.         TreeNode node1 = new TreeNode(1);
    3.         TreeNode node2 = new TreeNode(2);
    4.         TreeNode node3 = new TreeNode(3);
    5.         node1.left = node2;
    6.         //node1.right = node3;
    7.         List<List<Integer>> res ;
    8.         res = pathSum(node1,4);
    9.         System.out.println(res.size());
    11.     }
    12.     public static List<List<Integer>> pathSum(TreeNode root, int target) {
    13.         if(root == null ) new ArrayList<>();
    14.         List<List<Integer>> res = new ArrayList<>();
    15.         process(root, target, 0, new ArrayList<>(), res);
    16.         return res;
    17.     }
    18.     public static void process(TreeNode root, int target, int cur, List<Integer> list, List<List<Integer>> lists ){
    19.         if(root == null )return;
    20.         if(root.left == null && root.right==null ) {
    21.             if(cur + root.val == target){
    22.                 list.add(root.val);
    23.                 lists.add(list);
    24.             }
    25.             return ;
    26.         }
    27.         List<Integer> temp = new ArrayList<>();
    28.         temp.addAll(list);
    29.         temp.add(root.val);
    30.         process(root.left, target, cur + root.val, temp , lists);
    31.         List<Integer> temp2 = new ArrayList<>();
    32.         temp2.addAll(list);
    33.         temp2.add(root.val);
    34.         process(root.right, target, cur + root.val, temp2 , lists);
    36.     }
    37.     public static  class TreeNode {
    38.       int val;
    39.       TreeNode left;
    40.       TreeNode right;
    41.       TreeNode() {}
    42.       TreeNode(int val) { this.val = val; }
    43.       TreeNode(int val, TreeNode left, TreeNode right) {
    44.           this.val = val;
    45.           this.left = left;
    46.           this.right = right;
    47.       }
    48.   }

    看官方题解：
    image.png
    解法2: 广度优先，也要额外维护一个和队列，跟路径一一对应。
    通过深入理解回溯思想，改进代码

    1. public static void process(TreeNode root, int target, int cur, List<Integer> list, List<List<Integer>> lists ){
    2.         if(root == null )return;
    3.         if(root.left == null && root.right==null ) {
    4.             if(cur + root.val == target){
    5.                 List<Integer> temp = new ArrayList<>();
    6.                 temp.addAll(list);
    7.                 temp.add(root.val);
    8.                 lists.add(temp);
    9.             }
    10.             return ;
    11.         }
    12.         list.add(root.val);
    13.         process(root.left, target, cur + root.val, list , lists);
    14.         process(root.right, target, cur + root.val, list , lists);
    15.         list.remove(list.size()-1);
    17.     }

    时间从超过2.5%的用户提高到超过100%的用户。
    image.png