# python - unique bst II

• ``````# 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]
"""
if not n:

for i in range(2,n+1):
scratch = []

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))