```
class Solution(object):
def getatree(self, listt):
value = listt.pop()
if value == 0:
return None
node = TreeNode(value)
node.left = self.getatree(listt)
node.right = self.getatree(listt)
return node
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
theend = []
paraluniverse = [([],[range(1,n+1)])]
while paraluniverse:
(history, future) = paraluniverse.pop()
if future == []:
theend.append(history)
continue
tomorrow = future.pop()
if tomorrow == []:
history.append(0)
paraluniverse.append((history,future))
else:
for i in range(len(tomorrow)):
afuture = future[:]
ahistory = history[:]
ahistory.append(tomorrow[i])
afuture.append(tomorrow[i+1:])
afuture.append(tomorrow[:i])
paraluniverse.append((ahistory,afuture))
res = []
for fullhistory in theend:
fullhistory.reverse()
res.append(self.getatree(fullhistory))
return res
```