# 定义一个节点类
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 定义生成二叉搜索树的函数
def generateTrees(n):
    if n == 0:
        return []
    return generate_trees(1, n)

def generate_trees(start, end):
    if start > end:
        return [None,]
    all_trees = []
    for i in range(start, end + 1):  # 枚举可行根节点
        # 获得所有可行的左子树集合
        left_trees = generate_trees(start, i - 1)
        # 获得所有可行的右子树集合
        right_trees = generate_trees(i + 1, end)
        # 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
        for l in left_trees:
            for r in right_trees:
                curr_tree = TreeNode(i)
                curr_tree.left = l
                curr_tree.right = r
                all_trees.append(curr_tree)
    return all_trees

# 测试
n = 5
trees = generateTrees(n)
for tree in trees:
    print(tree.val)  # 打印根节点值