1. Given a binary tree, count all paths that equal to the target value starting from root. Leetcode: 113
2. Print all paths, Time complexity and Space complexity
3. Given a binary tree, count all paths that equal to the target value starting anywhere. Leetcode: 437
4. Print all paths, Time complexity and Space complexity

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> ans = new ArrayList<>();
    System.out.print(help(root, sum, new ArrayList<Integer>(), ans));
    return ans;
}
public int help(TreeNode root, int sum, List<Integer> list, List<List<Integer>> ans) {
    int count = 0;
    if (root == null) return 0;
    list.add(root.val);

    if (root.right == null && root.left == null && root.val == sum) {
        ans.add(new ArrayList<Integer>(list));
        count = 1;
        //list.remove(list.size() - 1);
        //return;
    }
    count += help(root.left, sum - root.val, list, ans);
    //list.remove(list.size() - 1);
    count += help(root.right, sum - root.val, list, ans);
    list.remove(list.size() - 1);
    return count;
}

//save path
class Solution { 
    List<List<Integer>> ans = new ArrayList<>();
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;

        int cur = pathSumNum(root, sum, new ArrayList<Integer>(), ans);
        int left = pathSum(root.left, sum);
        int right = pathSum(root.right, sum);
        System.out.println(ans);
        return cur + left + right;

    }
    public int pathSumNum(TreeNode root, int sum ,List<Integer> list,List<List<Integer>> ans) {
        if (root == null) return 0;
        list.add(root.val);
        if (sum == root.val){

            ans.add(new ArrayList<>(list));
            int left = pathSumNum(root.left, sum-root.val,list,ans);
            int right = pathSumNum(root.right, sum-root.val,list,ans);
            list.remove(list.size() - 1);

            return 1 + left + right;
        } else {
            int left = pathSumNum(root.left, sum-root.val,list,ans);
            int right = pathSumNum(root.right, sum-root.val,list,ans);
            list.remove(list.size() - 1);
            return left + right;
        }

    }
}

//using prefix sum
public int pathSum(TreeNode root, int sum) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);

        return help(root, sum, 0, map);
    }

    public int help(TreeNode root, int target, int preSum, Map<Integer,Integer> map) {
        if (root == null) return 0;
        preSum += root.val;
        //System.out.println(preSum);
        int count = map.getOrDefault(preSum - target,0);
        map.put(preSum,map.getOrDefault(preSum, 0) + 1);
        int left = help(root.left, target, preSum, map);
        //System.out.println(","+left);
        int right = help(root.right, target, preSum, map);
        //System.out.println(","+right);
        map.put(preSum,map.get(preSum) - 1);

        return count + left + right;
    }

iterative
//preodrer
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root  = stack.pop();
            root = root.right;
        }
        return list;
    }
}

//inodrer
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }

        }
        return list;
    }

}