```
class Solution(object):
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if not n:
return []
dp = [[None for j in xrange(n+1)] for i in xrange(n+2)]
for i in xrange(1, n+2):
dp[i][i-1] = [None]
# l length
for l in xrange(1, n+1):
for i in xrange(1, n-l+2):
j = i + l - 1
dp[i][j] = []
for k in xrange(i, j+1):
left_subtrees = dp[i][k-1]
right_subtrees = dp[k+1][j]
for lefttree in left_subtrees:
for righttree in right_subtrees:
root = TreeNode(k)
root.left = lefttree
root.right = righttree
dp[i][j].append(root)
return dp[1][n]
```