class Solution:
    def numTrees(self, n: int) -> int:
        cache=defaultdict(lambda:0)
        
        def dfs(n):
            if cache[n] != 0:
                return cache[n]
            
            if n == 0 or n == 1:
                return 1
            
            numT = 0
            for i in range(0, n):
                n1 = dfs(i)
                n2 = dfs(n-i-1)
                numT+=(n1*n2)
            cache[n] = numT
            return numT
            
        return dfs(n)
            
                

# 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]:
        
        cache=defaultdict(lambda:None)
        cache[1]=TreeNode(1)
        
        def dfs(l,n):
            
            if l > n:
                return [None]
            
            if l == n:
                return [TreeNode(l)]
            
            res=[]
            for i in range(l,n+1):
                L = dfs(l,i-1)
                R = dfs(i+1, n)
                for t1 in L:
                    for t2 in R:
                        node = TreeNode(i)
                        node.left = t1
                        node.right = t2
                        res.append(node)
            return res
        return dfs(1,n)