class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution():
    def generateTrees(self, n):
        def generateTrees(start, end):
            if start > end:
                return [None, ]

            allTrees = []
            for i in range(start, end + 1):  # 枚举可行根节点
                # 获得所有可行的左子树集合
                leftTrees = generateTrees(start, i - 1)

                # 获得所有可行的右子树集合
                rightTrees = generateTrees(i + 1, end)

                # 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
                print(start,end,i)
                print('l',[a for a in leftTrees])
                print('r', [a for a in rightTrees])
                for l in leftTrees:
                    for r in rightTrees:
                        print(i,l.val if l else None,r.val if r else None)
                        currTree = TreeNode(i)
                        currTree.left = l
                        currTree.right = r
                        allTrees.append(currTree)

            return allTrees

        return generateTrees(1, n) if n else []

if __name__ == '__main__':
    s = Solution()
    n = 3
    print(s.generateTrees(n))
