# My JAVA recursive solution--how to get the DP idea?

• ``````public class Solution {
public List<TreeNode> generateTrees(int n) {

List<TreeNode> contanier =new ArrayList<TreeNode>();

if (n<=0)  {
return contanier;
}

if (n==1){
return contanier;
}

//recursive method using 1 as root, 2 as root, 3 as root, ...
//and n as root
for (int i=1; i<=n; i++){

//for each i, get the left and right sub-trees, returns are the List
List<TreeNode> fromLeft=buildTree(1, i-1);
List<TreeNode> fromRight=buildTree(i+1, n);

//construct the final trees. if left sub-tree has N possibilities, right sub-tree has
//M possibilities, the final tree will have N*M possibilities.
for (int j=0; j<fromLeft.size(); j++){
for (int k=0; k<fromRight.size(); k++){
TreeNode temp=new TreeNode(i);
temp.left=fromLeft.get(j);
temp.right=fromRight.get(k);
}
}
}

return contanier;

}

public List<TreeNode> buildTree(int s, int e){
List<TreeNode> con =new ArrayList<TreeNode>();

if (e<s) {
return con;
}
if (e==s){
return con;
}

for (int i=s; i<=e; i++){
List<TreeNode> fromLeft=buildTree(s, i-1);
List<TreeNode> fromRight=buildTree(i+1, e);
for (int j=0; j<fromLeft.size(); j++){
for (int k=0; k<fromRight.size(); k++){
TreeNode temp=new TreeNode(i);
temp.left=fromLeft.get(j);
temp.right=fromRight.get(k);
}
}
}

return con;

}
``````

}

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