[LeetCode] Path Sum II

Thought:
Traditional BFS.
Note that in BFS algorithms, we should always keep the cache.add and the cache.remove in pairs.

Code:
public class Solution {
    public static ArrayList<Integer> cache;
    public static ArrayList<ArrayList<Integer>> result;
   
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        cache = new ArrayList<Integer>();
        result = new ArrayList<ArrayList<Integer>>();
        helper(root, sum);
        return result;       
    }
    public void helper(TreeNode root, int sum) {
        if (root == null) return;
        cache.add(root.val);
        sum = sum - root.val;
        if (root.left == null && root.right == null && sum == 0) result.add(new ArrayList<Integer>(cache));
        if (root.left != null) helper(root.left, sum);
        if (root.right != null) helper(root.right, sum); 
        cache.remove(cache.size() - 1);
    }
}

Code: 2013/8/15
public class Solution {
    public static ArrayList<ArrayList<Integer>> result;
    public static ArrayList<Integer> cache;
    public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
        result = new ArrayList<ArrayList<Integer>>();
        cache = new ArrayList<Integer>();
        dfs(root, sum, 0);
        return result;
    }
    public void dfs(TreeNode root, int target, int sum) {
        if (root == null) return;
        sum += root.val;
        cache.add(root.val);
        if (target == sum && root.left == null && root.right == null) {
            result.add(new ArrayList<Integer>(cache));
        }
        dfs(root.left, target, sum);
        dfs(root.right, target, sum);
        sum -= root.val;
        cache.remove(cache.size() - 1);
    }
    

}