Path Sum

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;

        List<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        dfs(root, path, root.val, target, res);
        return res;

    }

    public void dfs(TreeNode root, List<Integer> path, int sum, int target, List<List<Integer>> res) {
        if (root.left == null && root.right == null) {
            if (sum == target)
                res.add(new ArrayList<Integer>(path));
            return;
        }

        // go left
        if (root.left != null) {
            path.add(root.left.val);
            dfs(root.left, path, sum + root.left.val, target, res);
            path.remove(path.size() - 1);
        }

        // go right
        if (root.right != null) {
            path.add(root.right.val);
            dfs(root.right, path, sum + root.right.val, target, res);
            path.remove(path.size() - 1);
        }
    }
}

Path Sum II

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root the root of binary tree
     * @param target an integer
     * @return all valid paths
     */
    public List<List<Integer>> binaryTreePathSum2(TreeNode root, int target) {
        // Write your code here
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;

        List<Integer> path = new ArrayList<Integer>();
        path.add(root.val);
        dfs(root, path, root.val, target, res);
        return res;

    }

    public void dfs(TreeNode root, List<Integer> path, int sum, int target, List<List<Integer>> res) {

        // deal with solution for each dfs
        if (sum >= target) {
            int curSum = 0;
            List<Integer> solution = new ArrayList();

            for (int i = path.size()-1; i >= 0 ; i--) {
                curSum += path.get(i);
                solution.add(path.get(i));
                if (curSum == target) {
                    List<Integer> list = new ArrayList(solution);
                    Collections.reverse(list);
                    res.add(list);
                }
            }
        }

        // leaf node return to stop search
        if (root.left == null && root.right == null) {
            return;
        }


        // go left
        if (root.left != null) {
            path.add(root.left.val);
            dfs(root.left, path, sum + root.left.val, target, res);
            path.remove(path.size() - 1);
        }

        // go right
        if (root.right != null) {
            path.add(root.right.val);
            dfs(root.right, path, sum + root.right.val, target, res);
            path.remove(path.size() - 1);
        }
    }
}

Path Sum III [TO DO]