# A very simple and straight ans based on Math,Catalan Number ,O(N) times,O(1)space

• ``````    int numTrees(int n) {
//cantalan树
//C(2n,n)/(n+1)
long long ans =1;
for(int i=n+1;i<=2*n;i++){
ans = ans*i/(i-n);
}
return ans/(n+1);
}``````

• Simplified further:

``````int numTrees(int n) {
long long ans=1,i;
for(i=1;i<=n;i++)
ans = ans*(i+n)/i;
return ans/i;
}``````

• I found a summary of 50 applications of Catalan Number.
http://www-math.mit.edu/~rstan/ec/catalan.pdf

• nice solution, thanks alot

• Maybe not, but it's not hard to remember and it might be worth doing that. Catalan numbers have a lot of applications, as you can for example see from @cfjmonkey's link. Or if you understand a proof for it, you might be able to derive the formula from that when you need it.

• excellent solution

• @exspartacus
Could you please explain how we can we Catalan number is this case? I have a hard time understanding it.

• calculate the Cantalan numer or why is Cantalan number?
It is a math theory, you can find the similar proof stack pop sequence.
A equivalent problem the stack pop sequence.for exam, 1 2 3 4,the stack pop sequence may be 3 4 2 1, but 4 2 3 1 is wrong. each pop sequence is compared to mid-order transverse , while the origin sequence like 1 2 3 4 compared to pre-order transverse. And as you see, we can build the unique BST with the pre-order and mid-order.

• @StefanPochmann why not doing this :

``````int numTrees(int n) {
long long ans=1,i;
for(i=2;i<=n;i++)
ans = ans*(i+n)/i;
return ans;
}
``````

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