Java 2ms DP solution


  • 0
    T

    I take advantage of the solution from Unique Binary Search Trees. By passing in the count array to the helper function, we could easily create the result TreeNode array.

    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) return new ArrayList<TreeNode>();
        
        int[] count = new int[n+1];
        count[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                count[i] += count[j] * count[i - j - 1];
            }
        }
        
        TreeNode[] roots = helper(1, n, count);
        return Arrays.asList(roots);
    }
    
    private TreeNode[] helper(int start, int end, int[] count) {
        if (start > end) {
            TreeNode[] roots = new TreeNode[1];
            roots[0] = null;
            return roots;
        }
        
        TreeNode[] roots = new TreeNode[count[end - start + 1]];
        int index = 0;
        for (int i = start; i <= end; i++) {
            TreeNode[] lefts = helper(start, i - 1, count);
            TreeNode[] rights = helper(i + 1, end, count);
            for(TreeNode left : lefts) {
                for (TreeNode right : rights) {
                    roots[index] = new TreeNode(i);
                    roots[index].left = left;
                    roots[index++].right = right;
                }
            }
        }
        return roots;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.