Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from1ton.
Example 1:
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
Intuition
Approach 1: Formula
/*
2n
C
n
----
(n+1)
Catalan number
Since Double loses precision
We use repetative approach to calculate
nCk
6C3 = 6*5*4/3*2*1
Run for 1 to k
at each step multiply by n and divide by 1
*/
Approach 2 :
Using Dp
Lets take n = 2
1 2
Root as 1 ; Left = 0 right = 1 elements
Root as 2 ; Left = 1 right = 0 elements
n = 3
0 2
1 1
2 0
Add all
So on
Total n elements -> i ) 1 ( n-i-1
class Solution {
public:
int numTrees(int n) {
long long ans = 1;
int x = 2*n;
for(int i=1; i<=n; i++){
ans *= x;
x--;
ans /= i;
}
return ans / (n+1);
/*
2n
C
n
----
(n+1)
Catalan number
Since Double loses precision
We use repetative approach to calculate
nCk
6C3 = 6*5*4/3*2*1
Run for 1 to k
at each step multiply by n and divide by 1
*/
}
};
Approach 2:
Memoization
C++
class Solution {
public:
unordered_map<int,int> mp;
int numTrees(int n) {
if(n == 1 or n == 0)
return 1;
if(mp.find(n) != mp.end())
return mp[n];
int ans = 0;
for(int i=0; i<n; i++)
ans += numTrees(i) * numTrees(n-i-1);
return mp[n] = ans;
}
};
