不同的二叉搜索树 ii

class Solution:
    def __init__(self):
        # 使用备忘录存储优化
        self.memo = {}
    def generateTrees(self , n ):
        if n == 0:
            return [None]
        if n == 1:
            return [TreeNode(1)]
        # 使用数据范围做递归构树
        result = self.built(1, n)
        # 返回所有结果
        return result
    # 根据范围递归构树
    def built(self, start, end):
        if start > end:
            return [None]
        if start == end:
            return [TreeNode(start)]
        # 查询是否在备忘录中
        if (start, end) in self.memo:
            return self.memo[(start, end)]
        # 中间结果
        mid = []
        # 每个结点做根结点
        for i in range(start, end+1):
            # 选定i作为根,再递归构造所有可能的左右子树
            left = self.built(start, i-1)
            right = self.built(i+1, end)
            # 构造每一棵树
            for l in left:
                for r in right:
                    root = TreeNode(i)
                    root.left = l
                    root.right = r
                    # 存结果
                    mid.append(root)
        # 备忘录存储
        self.memo[(start, end)] = mid
        # 返回结果
        return self.memo[(start, end)]