Unique Binary Search Tree Problem: Given an integer n
, return the number of structurally unique BST’s (binary search trees) which has exactly n
nodes of unique values from 1
to n
.
Input: n = 3 Output: 5
Table of Contents
Unique Binary Search Tree Problem Solution
Problem Solution In Python
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
if n==0 or n==1:
return 1
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
for j in range(i):
dp[i]+=dp[i-j-1] * dp[j]
return dp[n]
Problem Solution In Java
public class Solution {
public int numTrees(int n) {
int[] record = new int[n+1];
record[0] = 1;
record[1] = 1;
return numTrees(n, record);
}
public int numTrees(int n, int[] record) {
int result = 0;
for(int i=1; i<=n; i++) {
int tmp = 1;
int left = i - 1;
int right = n - i;
if(record[left] > 0) {
tmp *= record[left];
} else {
tmp *= numTrees(left, record);
}
if(record[right] > 0) {
tmp *= record[right];
} else {
tmp *= numTrees(right, record);
}
result += tmp;
}
record[n] = result;
return result;
}
}
Problem Solution In C++
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i-j-1];
}
}
return dp[n];
}
};
Problem Solution In C
int solutions[1024]={1,1,};
int calculated = 1;
int numTrees(int n) {
if(n<calculated)
return solutions[n];
int start = calculated+1;
for(int loop = start;loop<n+1;loop++){
int sum = 0;
for(int i=0;i<loop;i++){
sum += solutions[i]*solutions[loop-i-1];
}
solutions[loop]=sum;
}
calculated = n;
return solutions[n];
}