1. class Solution:
    2.     def generateTrees(self, n):
    3.         """
    4.         :type n: int
    5.         :rtype: List[TreeNode]
    6.         """
    7.         def generate_trees(start, end):
    8.             if start > end:
    9.                 return [None,]
    11.             all_trees = []
    12.             for i in range(start, end + 1):  # pick up a root
    13.                 # all possible left subtrees if i is choosen to be a root
    14.                 left_trees = generate_trees(start, i - 1)
    16.                 # all possible right subtrees if i is choosen to be a root
    17.                 right_trees = generate_trees(i + 1, end)
    19.                 # connect left and right subtrees to the root i
    20.                 for l in left_trees:
    21.                     for r in right_trees:
    22.                         current_tree = TreeNode(i)
    23.                         current_tree.left = l
    24.                         current_tree.right = r
    25.                         all_trees.append(current_tree)
    27.             return all_trees
    29.         return generate_trees(1, n) if n else []