# 1 ms java solution beats 100.00%

• 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){
}
return res;
}
}
}``````

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

• 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;
}
``````

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