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/(in);
}
return ans/(n+1);
}
A very simple and straight ans based on Math,Catalan Number ,O(N) times,O(1)space

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

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.

@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 midorder transverse , while the origin sequence like 1 2 3 4 compared to preorder transverse. And as you see, we can build the unique BST with the preorder and midorder.