這一題看了幾個做法都是遞歸哎
# 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 generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n == 0:
return []
return self.generate(1, n)
def generate(self,start,end):
if start > end:
return [None]
if start == end:
return [TreeNode(start)]
res = []
for i in range(start, end+1):
leftnode = self.generate(start, i-1)
rightnode = self.generate(i+1, end)
for l in leftnode:
for r in rightnode:
root = TreeNode(i)
root.left = l
root.right = r
res.append(root)
return res
