Tuesday, November 18, 2014

Path Sum II LeetCode

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        if (root.left == null && root.right == null && sum == root.val) {
            List<Integer> curr = new ArrayList<Integer>();
            curr.add(root.val);
            result.add(curr);
            return result;
        }
        if (root.left != null) {
            List<List<Integer>> leftResults = pathSum(root.left, sum - root.val);
            for (int j=0; j<leftResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(leftResults.get(j));
                result.add(curr);
            }
        }
        if (root.right != null) {
            List<List<Integer>> rightResults = pathSum(root.right, sum - root.val);
            for (int j=0; j<rightResults.size();j++) {
                List<Integer> curr = new ArrayList<Integer>();
                curr.add(root.val);
                curr.addAll(rightResults.get(j));
                result.add(curr);
            }
        }
        return result;
    }

No comments:

Post a Comment