# Java 2ms recursive with memoization, and 3ms DP

• Recursive with memoization, very intuitive

``````public class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode>[][] treesForRange = (ArrayList<TreeNode>[][]) new ArrayList[n+2][n+1];
helper(1, n, treesForRange);
return treesForRange[1][n];
}

private void helper(int left, int right, List<TreeNode>[][] treesForRange) {
if (treesForRange[left][right] != null) {
return;
}
treesForRange[left][right] = new ArrayList<TreeNode>();
if (left > right) {
}
for (int root = left; root <= right; root++) {
helper(left, root - 1, treesForRange);
helper(root + 1, right, treesForRange);
for (TreeNode leftNode : treesForRange[left][root-1]) {
for (TreeNode rightNode : treesForRange[root+1][right]) {
TreeNode rootNode = new TreeNode(root);
rootNode.left = leftNode;
rootNode.right = rightNode;
}
}
}
}
}
``````

DP solution: basic idea is same as the previous recursive solution. It looks more lengthy and ugly, yet may save us from stack overflow.

``````public class Solution {
public List<TreeNode> generateTrees(int n) {
// DP, compute and store trees for intermediate ranges from 1 to n
// time: exponential, since for each range the number of trees is combinatorial
// space: O(n^2)
if (n == 0) {
List<TreeNode> result = new ArrayList<TreeNode>();
return result;
}
List<TreeNode>[][] treesForRange = (ArrayList<TreeNode>[][]) new ArrayList[n+2][n+1];
for (int step = 0; step < n; step++) {
for (int i = 1; i <= n - step; i++) {
int j = i + step;
treesForRange[i][j] = new ArrayList<TreeNode>();
if (step == 0) {
continue;
}
// k is a possible root for range i-j
for (int k = i; k <= j; k++) {
// two ugly if blocks for boundary cases:
// when k == i, the left subtree is null
// when k == j, the right subtree is null
if (treesForRange[i][k-1] == null) {
treesForRange[i][k-1] = new ArrayList<TreeNode>();
}
if (treesForRange[k+1][j] == null) {
treesForRange[k+1][j] = new ArrayList<TreeNode>();
}
for (TreeNode leftNode : treesForRange[i][k-1]) {
for (TreeNode rightNode : treesForRange[k+1][j]) {
TreeNode root = new TreeNode(k);
root.left = leftNode;
root.right = rightNode;
}
}
}
}
}
return treesForRange[1][n];
}
}``````

• This post is deleted!

• You can simplify the "ugly ifs" with `treesForRange[i][k-1] = Collections.singletonList(null);`, this also triggers a runtime error, so you need to create a `new List[][]` which is good practice anyway since you're not using the fact that you store `ArrayList`s.

Another way of making it nicer is to pre-fill the boundary cases before the `step` loop starts:

``````List<TreeNode> emptyTree = Collections.singletonList(null); // immutable list
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
treesForRange[i][j-1] = emptyTree;
treesForRange[j+1][i] = emptyTree;
}
}``````

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