```
public class Solution {
//construct a map which will be used to contain (Key, Values), which
//Key stands for the number of Integers, and
//Values stands for the number of valid Tree possibilities using the Key
//e.g. map.put(2,2); means for 2 integers it has 2 valid tree possiblities
HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
//initialize the map in the constructor
public Solution(){
map.put(0,1);
map.put(1,1);
map.put(2,2);
}
public int numTrees(int n) {
if (n<=1) return 1;
if (n==2) return 2;
int left;
int right;
int result=0;
//the idea is to calculate the numbers of valid tree possiblities
//when using 1 as root, 2 as root, 3 as root,...., and n as root
for (int i=1; i<=n; i++){
//calculate the number of possiblities of the left sub-tree;
if (map.get(i-1) !=null) {
//if we already have the number from the map,
//get that number from the map;
left=map.get(i-1);
}
else{
//if we do not have the number from the map,
//we calculate and put the number into the map
left=numTrees(i-1);
map.put(i,left);
}
//the same as calculating the left sub-tree
if (map.get(n-i) !=null) {
right=map.get(n-i);
}
else{
right=numTrees(n-i);
map.put(n-i,right);
}
//result should be left * right;
result+=left*right;
}
return result;
}
```

}