题解 | #二叉树根节点到叶子节点和为指定值的路径#

标准的递归回溯算法，题目小坑，又不说有没有负数
其实还可以广度遍历，记录每一条路径并记录其长度--或者最后算长度

int cur = 0;
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        //深度遍历，回溯算法
        ArrayList<Integer> con = new ArrayList<>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        DFS(root,con,sum,res);
        return res;
    }

    private void DFS(TreeNode root, ArrayList<Integer> con, int sum, ArrayList<ArrayList<Integer>> res) {
        if(root==null){
            return;
        }
        cur+=root.val;
        con.add(root.val);
        if (cur==sum&&root.left==null&&root.right==null){
            res.add(new ArrayList<>(con));
            //回退
            con.remove(con.size()-1);
            cur-=root.val;
            return;
        }
        DFS(root.left,con,sum,res);
        DFS(root.right,con,sum,res);
        //回退
        con.remove(con.size()-1);
        cur-=root.val;
    }