95. Unique Binary Search Trees II

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        
        return self.generate_trees(1, n) if n else []
    
    def generate_trees(self, start, end):
        all_trees = []
        
        # termination condition
        if start > end:
            return [None]
        
        # recursion rule
        for i in range(start, end + 1):
            # All possible left subtrees if i is chosen to be a root
            left_trees = self.generate_trees(start, i - 1)
            
            # All possible right subtrees if i is chosen to be a root
            right_trees = self.generate_trees(i + 1, end)
            
            # connect left and right subtrees to be the root i
            for l in left_trees:
                for r in right_trees:
                    current_tree = TreeNode(i)
                    current_tree.left = l
                    current_tree.right = r
                    all_trees.append(current_tree)
        return all_trees