# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def gen_trees(start, end):
if start > end:
return [None]
trees = []
for i in range(start, end + 1):
left_trees = gen_trees(start, i - 1)
right_trees = gen_trees(i + 1, end)
for lt in left_trees:
for rt in right_trees:
root = TreeNode(i + 1, left=lt, right=rt)
trees.append(root)
return trees
return gen_trees(0, n - 1) if n else []