JZ24-二叉树中和为某一值的路径

class Solution {
    ArrayList<ArrayList<Integer>> out = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        if (root == null) {
            return out;
        }
        backtracking(root, target, new ArrayList<>());
        return out;
    }

    public void backtracking(TreeNode root, int target, ArrayList<Integer> in) {
        if (root == null) {
            return;
        }
        in.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null) {
            out.add(new ArrayList<>(in));  //ArrayList<ArrayList<Integer> in>
        } else {
            backtracking(root.left, target, in);//回溯法，分别尝试不同方向
            backtracking(root.right, target, in);
        }
        in.remove(in.size() - 1);
        // 8 9 2 4 -> 8 9 2 1(把2的左子树4删去，重新加上1)
        //代码走到这里，表明要回溯，代表当前path中的root节点我已经不需要了
    }
}