* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> res = new ArrayList<>();
if (n == 0) {
return res;
}
TreeNode tree = new TreeNode(1);
res.add(tree);
for (int i = 2; i <= n; i++) {
int lastSize = res.size();
for(int j = 0; j < lastSize; j++) {
TreeNode currTree = res.get(0);
TreeNode newTree = null;
for (int k = 1; k < i; k++) {
if (newTree == null) {
newTree = clone(currTree);
}
if (insertAfter(i, k, newTree)) {
res.add(newTree);
newTree = null;
}
}
newTree = new TreeNode(i);
newTree.left = currTree;
res.add(newTree);
res.remove(0);
}
}
return res;
}
public boolean insertAfter(int item, int key, TreeNode tree) {
TreeNode curr = tree;
while (curr.val != key) {
if ((item - curr.val) * (key - curr.val) < 0) {
return false;
}
if (key < curr.val) {
curr = curr.left;
} else {
curr = curr.right;
}
}
TreeNode tmp = new TreeNode(item);
if (curr.right != null) {
tmp.left = curr.right;
}
curr.right = tmp;
return true;
}
public TreeNode clone(TreeNode tree) {
TreeNode copy = new TreeNode(tree.val);
clone(tree, copy);
return copy;
}
public void clone(TreeNode tree, TreeNode copy) {
if (tree == null) {
return;
}
if (tree.left != null) {
copy.left = new TreeNode(tree.left.val);
clone(tree.left, copy.left);
}
if (tree.right != null) {
copy.right = new TreeNode(tree.right.val);
clone(tree.right, copy.right);
}
}
}