递归的思路

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if(root == null)
            return res;
        if(root.left == null && root.right == null && root.val == target){//每次递归到叶子节点就把节点添加到路径中，要保证
            ArrayList<Integer> t = new ArrayList<>();
            t.add(target);
            res.add(t);
            return res;
        }
        ArrayList<ArrayList<Integer>> rL = FindPath(root.left,target - root.val);
        ArrayList<ArrayList<Integer>> rR = FindPath(root.right,target - root.val);
        addF(rL,root.val);addF(rR,root.val);
        for(int i = 0;i < rR.size();i++)
            rL.add(rR.get(i));
        return rL;
    }
    public void addF(ArrayList<ArrayList<Integer>> a,int val){
        for(ArrayList<Integer> aa : a){
            aa.add(0,val);
        }
    }
}

• 几个要点：
  • 想到要用递归，并且确定好递归每次结束的链表合并
  • 看到被人说的检验不检查是否按照长度排序，有空再回来看看有序合并
  • 递归思路：空节点直接返回，如果直接是叶子节点并且值和给定的target值相等，就直接产生一个长度为1的路径，然后添加到返回的只有一种路径的的总链表中；如果这两种情况都不满足，就减去根节点的值，递归调用左子树和右子树，合并起来，都加头节点然后返回