Solution : Java + DP

amazon
Tags: #<Tag:0x00007f24264abd60>

#1

public class Solution {
public ArrayList generateTrees(int n) {
ArrayList<ArrayList> list = new ArrayList<ArrayList>();
ArrayList o = new ArrayList();
list.add(o);
o.add(null);
TreeNode temp = new TreeNode(1);
ArrayList part = new ArrayList();
part.add(temp);
list.add(part);
for(int i=2;i<=n;i++){
part = new ArrayList();
for(int j=1;j<=i;j++){
for(int m=0;m<list.get(j-1).size();m++){
for(int k=0;k<list.get(i-j).size();k++){
TreeNode temp1 = new TreeNode(j);
temp1.left = list.get(j-1).get(m);
int val = j;
temp1.right = search(list.get(i-j).get(k),val);
part.add(temp1);
}
}
}
list.add(part);
}
return list.get(n);
}

public static TreeNode search(TreeNode root,int val){
    if(root==null)return null;
    TreeNode result = new TreeNode(root.val+val);
    result.left = search(root.left,val);
    result.right = search(root.right,val);
    return result;
}

}