```
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def copy(self, root):
ret = None
if root:
ret = TreeNode(root.val)
ret.left = self.copy(root.left)
ret.right = self.copy(root.right)
return ret
def insert(self, root, curr, ht):
# special insert routine assumes
# that number to be inserted is greater
# than all numbers in the tree
level, ret, prev = 0, self.copy(root), None
while level < ht:
prev, level = prev.right if prev else ret, level + 1
curr.left = prev.right if prev else ret
if prev:
prev.right = curr
else:
ret = curr
return ret
def is_leaf(self, node):
return node.left == None and node.right == None
def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
answer = []
if not n:
return answer
answer = [TreeNode(1)]
for i in range(2,n+1):
scratch = []
for tree in answer:
curr, ht = TreeNode(i), 0
scratch.append(self.insert(tree, curr, ht))
# add the next greatest number into a tree from
# existing set of trees. start from the root
# and trickle it down to the last level.
# the next greatest number will be the right most leaf.
# use a copy-on-write approach for each insertion into
# the tree. insert the number into a copy of the tree.
while not self.is_leaf(curr):
curr, ht = TreeNode(i), ht + 1
scratch.append(self.insert(tree, curr, ht))
answer = scratch
return answer
```