[java/3ms] DP, using list<TreeNode>[]

• From Unique BST 1, we have DP transformation formula, `BST[i] = sum{BST[j] + BST[i-1-j]}, for j = 0...i-1`. That is, `#BST with j nodes on left + #BST with i-1-j nodes on right`, regardless of the actual values in the BST.

But here, we have to care about the actual tree value. So, I use `offset` on trees I've already generated.

template[i] means all possible BSTs generated from 0...i, for further understanding, you can think it just as BST with i nodes.

``````public List<TreeNode> generateTrees(int n) {
if (n < 1)
return new ArrayList<>();

List<TreeNode>[] template = new ArrayList[n+1];
List<TreeNode> zero = new ArrayList<>();
template[0] = zero;

for (int i = 1; i <= n; i++) {
List<TreeNode> tmp = new ArrayList<>();
for (int j = 0; j < i; j++) {
for (TreeNode left_root : template[j]) {
for (TreeNode right_root: template[i-1-j]) {
TreeNode root = new TreeNode(j+1);
root.left = generator(left_root, 0);
root.right = generator(right_root, j+1);
}
}
}
template[i] = tmp;
}

return template[n];
}

private TreeNode generator(TreeNode root, int offset) {
if (root == null)
return root;
TreeNode _root = new TreeNode(root.val + offset);
_root.left = generator(root.left, offset);
_root.right = generator(root.right, offset);
return _root;
}
``````

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