1 ms java solution beats 100.00%


  • 2
    N

    Firstly, we calculate the total number of BST's with nodes 1 to n using dp. Then we konw definitely how many nodes need to be stored. So we can use Array rather than List.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode[] recursion(int s, int e, int[] dp){
            TreeNode[] roots = null;
            int curlen = 0;
            if(s > e){
                roots = new TreeNode[1];
                roots[0] = null;
                return roots;
            }
            roots = new TreeNode[dp[e - s + 1]];
            for(int i = s; i <= e; i++){
                TreeNode[] lefts = recursion(s, i - 1, dp);
                TreeNode[] rights = recursion(i + 1, e, dp);
                for(TreeNode left : lefts){
                    for(TreeNode right : rights){
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        roots[curlen++] = root;
                    }
                }
            }
            return roots;
        }
        public List<TreeNode> generateTrees(int n) {
            if(n == 0)
                return new ArrayList<TreeNode>();
            else{
                int[] dp = new int[n + 1];
                dp[0] = 1;
                dp[1] = 1;
                for(int i = 2; i <= n; i++)
                    for(int j = 1; j <= i; j++)
                        dp[i] += dp[j - 1] * dp[i - j];
                TreeNode[] resarr =  recursion(1, n, dp);
                List<TreeNode> res = new ArrayList<>();
                for(TreeNode node : resarr){
                    res.add(node);
                }
                return res;
            }
        }
    }

  • 0
    N

    when n=15, it cost 15s,because it's a Divide-and-conquer , not dp


  • 0
    M

    First calculating the number of sub-trees is a good approach. Avoids realloc and makes for a relatively clean looking C code. Solution with memorization is given below. Full source can be accessed at the bit bucket link

    /*
    ** genbstnum: Recursively generate number of unique BSTs.
    */
    void genbstnum(int s, int e, int sz, int *dp)
    {
        int i, dpoff = DPOFF(s, sz, e);
    
        /* If value cached, then return. */
        if (dp[dpoff]) return;
    
        /* Loop from the start to the end selecting different root values. */
        for (i = s; i <= e; ++i)
        {
            /* Generate number of left and right sub-trees */
            genbstnum(s, i - 1, sz, dp);
            genbstnum(i + 1, e, sz, dp);
            dp[dpoff] += dp[DPOFF(s, sz, i - 1)] * dp[DPOFF(i + 1, sz, e)];
        }
    
        /* NULL terminations are set to 1 */
        dp[dpoff] = dp[dpoff] == 0 ? 1: dp[dpoff];
    }
    
    /*
    ** genbst: Generate unique BSTs from a list of numbers
    */
    struct TreeNode **genbst(int start, int end, int sz,
                             struct TreeNode ***dpt, int *dpsz)
    {
        int i, j, k, cnt = 0, dpoff = DPOFF(start, sz, end);
        struct TreeNode **bst_arr = NULL, **lbst_arr, **rbst_arr;
        struct TreeNode *root;
    
        /* If valid, then return the cached value */
        if (dpt[dpoff] != NULL)
            return dpt[dpoff];
    
        /* Initialize array with the number of entries. */
        if ((bst_arr  = calloc(dpsz[dpoff], sizeof(struct TreeNode *))) == NULL)
            return NULL;
    
        /* Loop from the start to the end selecting different root values. */
        for (i = start; i <= end; ++i)
        {
            /* Generate left and right sub-trees */
            lbst_arr = genbst(start, i - 1, sz, dpt, dpsz);
            rbst_arr = genbst(i + 1, end, sz, dpt, dpsz);
    
            /* Generate all possible combinations with i as the root */
            for (j = 0; j < dpsz[DPOFF(start, sz, i - 1)] && lbst_arr; ++j)
                for (k = 0; k < dpsz[DPOFF(i + 1, sz, end)] && rbst_arr; ++k)
                {
                    /* Allocate root */
                    if ((root = malloc(sizeof(struct TreeNode))) == NULL)
                        return NULL;
                    root->val = i;
    
                    /* Assign left and right sub-trees and root. */
                    root->left = lbst_arr[j];
                    root->right = rbst_arr[k];
                    bst_arr[cnt++] = root;
                }
        }
    
        /* Update the cache */
        dpt[dpoff] = bst_arr;
        return bst_arr;
    }
    

Log in to reply
 

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