# Accepted recursive solution with hashmap optmization.

• ``````public class Solution {
HashMap<Integer, ArrayList<ArrayList<TreeNode>>>map = new HashMap<>();
public List<TreeNode> generateTrees(int n) {
ArrayList<TreeNode> list = new ArrayList<>();
if(n==0)return list;
return gen(1, n);
}
private ArrayList<TreeNode> gen(int s, int e){
ArrayList<TreeNode> list;
if(e==s){
list=new ArrayList<>();
return list;
}
if(map.containsKey(e-s)&&map.get(e-s).size()>=s){
return map.get(e-s).get(s-1);
}
list = new ArrayList<>();
for(int i=e; i>=s; i--){
ArrayList<TreeNode> leftList;
if(i>s)leftList=gen(s, i-1);
else{
leftList=new ArrayList<>();
}
ArrayList<TreeNode> rightList;
if(i+1<=e)rightList = gen(i+1, e);
else{
rightList=new ArrayList<>();
}
for(int l=0; l<leftList.size(); l++){
for(int r=0; r<rightList.size(); r++){
TreeNode root = new TreeNode(i);
root.left=leftList.get(l);
root.right=rightList.get(r);
}
}
}
ArrayList<ArrayList<TreeNode>> mapList;
if(map.containsKey(e-s)){
mapList=map.get(e-s);
}
else{
mapList= new ArrayList<>();
map.put(e-s, mapList);
}

return list;
}
}``````

• could you explain what are arguments s and e in the gen function and what the meaning of second argument in map type?

• the gen function generates all binary trees from s to e. the map stores previously found tree structure based on the number of nodes in a List<List<TreeNode> . then it is further indexed by the value of the head node.

i hope that helps

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.