# Simple C++ code with explaination. 0ms

• ``````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

1. the elements are not repeated
2. any elements of 1~n can be the root
3. 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)
4. use a hashmap to store previously calculated numTrees to avoid redundant calculation

• Time limit exceeded when n=19.

• Time is not 4ms！！

• Test data have been updated already.