Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Similar to Path Sum I, but this time we need to use a list to track the visited path and remove the node from the current path after recursively visited all paths through the node.

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        if (root==null) {
            return results;
        }

        pathSum(results, new ArrayList<Integer>(), 0, root, sum);

        return results;
    }

    public void pathSum(List<List<Integer>> results, List<Integer> currentPath, int currentSum, TreeNode root, int sum) {
        if (root.left==null&&root.right==null) {
            if (currentSum+root.val==sum) {
                List<Integer> result = new ArrayList<Integer>(currentPath);
                result.add(root.val);
                results.add(result);
            }
            return;
        }

        currentPath.add(root.val);
        if (root.left!=null) {
            pathSum(results, currentPath, currentSum+root.val, root.left, sum);
        }
        if (root.right!=null) {
            pathSum(results, currentPath, currentSum+root.val, root.right, sum);
        }
        currentPath.remove(currentPath.size()-1);

    }