http://www.lintcode.com/en/problem/binary-tree-path-sum-ii/\#

the problem of this is totally different from the Binary Tree Path Sum I where we only care about the sum from root to the leaf. here, every straight down path that has a sum of the target we have to include. so my approach is to have a function to calculate the path from top down along the way, meaning the path starting point is set to be the root. and another function take us pre-traveral. so every node is acting as root one time to go through the first function.

    int sum = 0;
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        List<Integer> cur = new ArrayList<>();
        traverseHelper(root, target, ans);
        return ans;
    }

    public void traverseHelper(TreeNode root, int target, List<List<Integer>> ans) {

        if (root == null) {
            return;
        }

        List<Integer> cur = new ArrayList<>();
        TreeNode tempRoot = root;
        countHelper(tempRoot, target, ans, cur);

        traverseHelper(root.left, target, ans);
        traverseHelper(root.right, target, ans);

    }


    public void countHelper(TreeNode root,int target, List<List<Integer>> ans, List<Integer> cur) {
        if (root == null) {
            return;
        }

        cur.add(root.val);
        sum = sum + root.val;

        if (sum == target) {
            ans.add(new ArrayList<Integer>(cur));
        }

        countHelper(root.left, target, ans, cur);
        countHelper(root.right, target, ans, cur);

        sum = sum - cur.get(cur.size() - 1);
        cur.remove(cur.size() - 1);
    }