Friday, November 21, 2014

Unique Binary Search Trees II LeetCode

Recursion could simplify the code significantly.
The returning result is all the root node of each Tree.

public List<TreeNode> generateTrees(int n) {
        return generateTrees(1,n);
    }
    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();
       
        if (start > end) {
            result.add(null);
            return result;
        }
        for (int i=start; i<=end; i++) {
            for (TreeNode left : generateTrees(start, i-1)) {
                for (TreeNode right : generateTrees(i+1, end)) {
                    TreeNode curr = new TreeNode(i);
                    curr.left = left;
                    curr.right = right;
                    result.add(curr);
                }
            }
        }
        return result;
    }

No comments:

Post a Comment