剑指offer---二叉树中和为某一值的路径集合

import java.util.ArrayList;
import java.util.Collections;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>>res = new ArrayList<>();
        if(root == null)
            return res;
        int sum = 0;
        ArrayList<Integer>path = new ArrayList<>();
        preOrder(root,sum,target,path,res);
        Collections.sort(res,(left,right)->{
            return left.size()>right.size()?-1:1;
        });
            return res;
    }
    public void preOrder(TreeNode root,int sum,int target,ArrayList<Integer>path,ArrayList<ArrayList<Integer>>res){
        if(root==null)
            return;
        path.add(root.val);
        sum+=root.val;
        if(root.left==null&&root.right==null){
            if(sum==target)
//注意要复制一个list
                res.add(new ArrayList<Integer>(path));
        }
        preOrder(root.left,sum,target,path,res);
        preOrder(root.right,sum,target,path,res);
        path.remove(path.size()-1);
    }
}

说一百遍也不为过，注意注释：要复制一个list，如果直接add(path),因为path都是指向同一个对象的，后面的修改也会影响到之前已经加入的path，而且加入的每个path都是一致的！！！！