When I saw this question, I found a solution for this in a minute. And here is my solution:

```
int numTrees(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
if(n == 2) return 2;
int result = 0;
for(int i = 0 ; i < n ; i++)
{
result += (numTrees(i) * numTrees(n-i-1));
}
return result;
}
```

But apparently, the time complexity is way too big. I am not sure how to estimate the complexity here, could anyone give me some hints for this? Thanks.

Also, I improve this method by using an array to store the numbers needed to calculate the result. I think for this one which is accepted, the time complexity is O(n) since it has to set up the array first. But the space complexity is also O(n), am I correct?

```
vector<int> temp_arr;
int numTrees(int n) {
if(n == 0) return 1;
if(n == 1) return 1;
if(n == 2) return 2;
temp_arr.resize(n+1);
temp_arr[0] = 1; // n == 0
temp_arr[1] = 1; // n == 1
temp_arr[2] = 2; // n == 2
for(int i = 3 ; i <= n ; i++)
{
helper(i);
}
return temp_arr[n];
}
int helper(int x) {
int result = 0;
for(int i = 0 ; i < x ; i++)
{
result += (temp_arr[i] * temp_arr[x-i-1]);
}
temp_arr[x] = result;
return result;
}
```