# My AC Java Solution without recursive

• My answer is below, is it use DP? or can it be more effective?

``````/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; left = null; right = null; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {

//key为数字，value是1到数字key这个序列，可以生成的所有BST的根结点List
Map<Integer, List<TreeNode>> list = new HashMap<Integer, List<TreeNode>>();
List<TreeNode> temp0 = new ArrayList<TreeNode>();
list.put(0, temp0);   //注意这里，当n为0时，依然需要创建temp0，只是temp0里面没有任何元素，也就是没有满足条件的BST

if(n < 1)
return list.get(0);

List<TreeNode> temp1 = new ArrayList<TreeNode>();
list.put(1, temp1);

for(int i = 2; i <= n; i++)
{
List<TreeNode> l = new ArrayList<TreeNode>();
List<TreeNode> preL = list.get(i-1);  //想求f(n)要获得f(n-1)
Iterator<TreeNode> it = preL.iterator();
while(it.hasNext())
{
TreeNode root = cloneTree(it.next());   //注意，这里要对树进行复制，要不然会直接修改f(n-1)里的树
TreeNode rootClone = cloneTree(root);   //克隆两次，一个是root用于第一种情况，另一个是rootClone用于第二种情况
l.add(constructTree(root, new TreeNode(i)));   //第一种情况：将i作为原来BST的最右结点
TreeNode node = new TreeNode(i);
node.left = rootClone;   //第二种情况：将原来的BST作为i的左子树
}
for(int j = 1; j < i-1; j++)
{
List<TreeNode> l1 = list.get(j);   //f(j)
List<TreeNode> l2 = list.get(i-j-1);   //f(i-j-1)
Iterator<TreeNode> it1 = l1.iterator();

while(it1.hasNext())   //f(j)和f(i-j-1)两者相乘
{
TreeNode node1 = it1.next();
Iterator<TreeNode> it2 = l2.iterator();
while(it2.hasNext())
{
TreeNode root1 = cloneTree(node1);   //克隆f(j)里的树
TreeNode root2 = changeData(cloneTree(it2.next()), j);   //先克隆f(i-j-1)里的树，然后改变root2里结点的值
TreeNode node = new TreeNode(i);
TreeNode root3 = constructTree(root1, node);   //将i连接进root1
node.left = root2;   //连接node和root2，即：将i的左子树赋为root2
}
}
}
list.put(i, l);
}

return list.get(n);
}

//将结点node插入树root中，满足node是root中最右边的结点，即满足node是中序遍历时最后一个结点
public TreeNode constructTree(TreeNode root, TreeNode node) {
TreeNode temp = root;
TreeNode preTemp = null;
while(temp != null)
{
preTemp = temp;
temp = temp.right;
}
if(preTemp != null)
preTemp.right = node;

return root;
}

public TreeNode cloneTree(TreeNode root) {   //克隆树
TreeNode rootClone = new TreeNode(root.val);
if(root.left != null)
rootClone.left = cloneTree(root.left);
if(root.right != null)
rootClone.right = cloneTree(root.right);
return rootClone;
}

public TreeNode changeData(TreeNode root, int diff) {   //改变树中结点的值，每个结点的值增大diff
root.val += diff;
if(root.left != null)
changeData(root.left, diff);
if(root.right != null)
changeData(root.right, diff);
return root;
}
}``````

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