```
class Solution{
unordered_map<int, int> res;
public:
int numTrees(int n){
if (n <= 0 || n == 1)
return max(n, 0);
int ret = 0;
for(int i = 1; i <= n; i++){
if(i == 1 || i == n){
int first = 0, second = 0;
if(res.find(n - 1) == res.end()){
first = numTrees(n - 1);
res[n - 1] = first;
}else
first = res[n-1];
ret += first;
}
else{
int first = 0, second = 0;
if(res.find(i - 1) == res.end()){
first = numTrees(i - 1);
res[i - 1] = first;
}else
first = res[i-1];
if(res.find(n - 1) == res.end()){
second = numTrees(n - i);
res[n-i] = second;
}else
second = res[n-i];
ret += first * second;
}
}
return ret;
}
};
```

the idea is :

using an hashmap to store the numTrees that have been calculated to aviod repeat calculation

- the elements are not repeated
- any elements of 1~n can be the root
- the root, i , has one/ two children, left :(0~i-1) , right : (i + 1

~ n), at this situation, the numTree of this root is numTree(i - 1)

* numTree(n - i ). if i == 1 or i == n, it's numTree(n - 1) - use a hashmap to store previously calculated numTrees to avoid redundant calculation