class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution():
def generateTrees(self, n):
return self.buildTree(0, n)
def buildTree(self, n1, n2):
if n1==n2:
return [None]
if n1+1 == n2:
node = TreeNode(n1+1)
node.left = None
node.right = None
return [node]
else:
results = []
for x in range(n1, n2):
left_list = self.buildTree(n1, x)
right_list = self.buildTree(x+1, n2)
for left in left_list:
for right in right_list:
node = TreeNode(x+1)
node.left = left
node.right = right
results.append(node)
return results
class TreeNode():
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution():
def generateTrees(self, n):
return self.generateTreesRecu(1, n)
def generateTreesRecu(self, low, high):
result = []
if low > high:
result.append(None)
for i in range(low, high + 1):
left = self.generateTreesRecu(low, i - 1)
right = self.generateTreesRecu(i + 1, high)
for j in left:
for k in right:
cur = TreeNode(i)
cur.left = j
cur.right = k
result.append(cur)
return result
if __name__ == "__main__":
print(Solution().generateTrees(3))