A bottom-up DP solution and a top-down recursive solution.

• Top-down recursive solution

``````class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0: return []
return self.helper(1,n)

def helper(self, i, j):
if i > j:
return [None]

res = []
for n in xrange(i, j+1):
left_nodes = self.helper(i, n-1)
right_nodes = self.helper(n+1, j)
for left_node in left_nodes:
for right_node in right_nodes:
node = TreeNode(n)
node.left = left_node
node.right = right_node
res.append(node)

return res
``````

Bottom-up DP

``````class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
if (n==0) return {};

vector<vector<vector<TreeNode*>>> dp(n+2, vector<vector<TreeNode*>>(n+2));

for (int i=0; i<=n+1; ++i)
for (int j=0; j<=n+1; ++j)
if (i > j)
dp[i][j].push_back(nullptr);

for (int len = 1; len <= n; ++len) {

for (int i = 1; i <= n - len + 1; ++i) {
int j = i+len-1;
for (int k = i; k <= j; k++) {
for (auto &l: dp[i][k-1]) {
for (auto &r: dp[k+1][j]) {
auto node = new TreeNode(k);
node->left = l;
node->right = r;
dp[i][j].push_back(node);
}
}
}
}
}

return dp[1][n];
}
};
``````

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