# Java 2ms efficient DP heuristic solution

• The general DP way of solving this problem is construct the tree from 0, 1, 2 .. until n nodes. The keys is: there are only three ways to add new node with higher value on top of all the current trees with lower value. Details are explained in comments.

``````    public List<TreeNode> generateTrees(int n) {
ArrayList<TreeNode> nodes = new ArrayList<>();
if (n == 0) return nodes;
nodes.add(new TreeNode(1));
for (int i = 2; i <= n; i++){
ArrayList<TreeNode> newNodes = new ArrayList<>();
for (TreeNode treeNode: nodes){
// 1. Add new node on right top of original tree
TreeNode newRoot = new TreeNode(i);
newRoot.left = copyTreeNode(treeNode);
newNodes.add(newRoot);
TreeNode nextRoot = treeNode;

// 2. Add new node on all most right edges of the original tree
while (nextRoot.right != null){
TreeNode next = copyTreeNode(treeNode);
newNodes.add(next);
// find the current right edge in the newly copied tree
while (next.val != nextRoot.val){
next = next.right;
}

TreeNode breakNode = new TreeNode(i);
breakNode.left = next.right;
next.right = breakNode;
// next right edge
nextRoot = nextRoot.right;
}

// 3. Add new node on the most right-bottom of original tree
nextRoot.right = new TreeNode(i);
}
nodes.addAll(newNodes);
}
return nodes;
}

private TreeNode copyTreeNode(TreeNode treeNode){
if (treeNode == null) return null;
TreeNode newNode = new TreeNode(treeNode.val);
newNode.left = copyTreeNode(treeNode.left);
newNode.right = copyTreeNode(treeNode.right);
return newNode;
}
``````

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