二叉树节点为某一值的路径

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

思路：要寻找到所有路径，可以使用DFS，要保证最后的和一定就行。保证按数组大小排序，可以使用优先队列来实现。

public class Solution {
   //根据列表长度排序
    PriorityQueue<ArrayList<Integer>> pathList = new PriorityQueue<>(new Comparator<ArrayList<Integer>>() {
        @Override
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            return o2.size() - o1.size();
        }
    });
 
     ArrayList<ArrayList<Integer>> newPathList= new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
 
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) return newPathList;
        DFS(root, target);
        //调整数组顺序
        while (!pathList.isEmpty()){
            newPathList.add(pathList.poll());
        }
        return  newPathList;
    }
    public void DFS(TreeNode root, int target) {
        path.add(root.val);
        if (root.left == null&&root.right==null&&target==root.val) {
                pathList.add(new ArrayList<Integer>(path));      //直接add(path)会有魔法出现，导致最终结果为空
//应该是这样的原因,未new时,path的两次结果会一致，因为是指向同一对象
        }
        //递归
       if(root.left!=null) DFS(root.left, target - root.val);
        if(root.right!=null)DFS(root.right, target - root.val);
        //回退到父节点
        path.remove(path.size() - 1);
    }
}