Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:


Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Difficulty: interview

Starter code:

# 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]:
        

Solutions:
"""
 of course this is a dp problem.
 if we consider upper bound and lower bound for each sub tree, 
 we will have a index-based solution over all posible numbers.
 
 each time we part a sub-tree into two parts, the question then becomes:
 how many possible boundaries can we find (start, end).
 """
 
 class Solution:
     def generateTrees(self, n):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         dp = dict()
         ret = self.generate_recursively(list(range(1, n+1)), 0, n, dp)
         if n == 0:
             ret = []
         return ret
 
     # list is a sorted list of trees
     def generate_recursively(self, l, start, end, dp):
         ret = []
         if end - start == 1:
             ret = [TreeNode(l[start]),]
         elif end - start <= 0:
             ret = [None,]
 
         # take each index as partition place
         else:
             for idx in range(0, end - start):
                 left_nodes = dp[(start, start+idx)] if (start, start+idx) in dp.keys() else self.generate_recursively(l, start, start+idx, dp)
                 right_nodes = dp[(start+idx+1, end)] if (start+idx+1, end) in dp.keys() else self.generate_recursively(l, start+idx+1, end, dp)
 
                 for left in left_nodes:
                     for right in right_nodes:
                         root = TreeNode(l[start+idx])
                         root.left = left 
                         # if left != '<E>' else None
                         root.right = right 
                         # if right !='<E>' else None
                         ret.append(root)
         dp[(start, end)] = ret
         return ret
 
 s = Solution()
 s.generateTrees(3)

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if n <= 0:
             return []
         
         mem = {}
         
         return self.genTrees(mem, 1, n)
     
     def genTrees(self, mem, start, end):
         cached = mem.get((start, end))
         if cached != None:
             return cached
         
         if start > end:
             return [None]
         
         if start == end:
             return [TreeNode(start)]
         
         retVal = []
         for i in range(start, end + 1):
             left = self.genTrees(mem, start, i - 1)
             right = self.genTrees(mem, i + 1, end)
             
             for lnode in left:
                 for rnode in right:
                     root = TreeNode(i)
                     root.left = lnode
                     root.right = rnode
                     retVal.append(root)
 
         mem[(start, end)] = retVal
         return retVal


# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         
         if n == 0:
             return []
         
         root_dict = dict()
         
         def recur(start, end):
             if start > end:
                 return [None]
             
             rl = root_dict.get((start, end))
             if not rl:
                 rl = []
                 for v in range(start, end+1):
                     for lc in recur(start, v-1):
                         for rc in recur(v+1, end):
                             root = TreeNode(v)
                             root.left, root.right = lc, rc
                             rl.append(root)
                             
                 root_dict[(start, end)] = rl
                 
             return rl
                         
         return recur(1, n)
                         

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         
         if n < 1: return []
         
         def genTrees(trees, i, j):
             if (i, j) in trees: return trees[(i, j)]
             if i > j: return [None]
             
             trees[(i, j)] = []
             
             for k in range(i, j + 1):
                 leftTrees = genTrees(trees, i, k-1) 
                 rightTrees = genTrees(trees, k+1, j)
                 newTrees = []
                 for l in leftTrees:
                     for r in rightTrees:
                         newNode = TreeNode(k)
                         newNode.left = l
                         newNode.right = r
                         newTrees.append(newNode)
                 trees[(i, j)] += newTrees
                 
             return trees[(i, j)]
         
         trees = {}
         return genTrees(trees, 1, n)
         
         

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if not n:
             return []
         all_tress = {}
         for r in range(1, n+1):
             for start in range(1, n+2-r):
                 end = start + r - 1
                 all_tress[self.to_key(start, end)] = []
                 if r == 1:
                     all_tress[str(start) + str(end)] = [TreeNode(start)]
                 else:
                     for index_root in range(start, end + 1):
                         left_trees = all_tress.get(self.to_key(start, index_root - 1), [None])
                         right_trees = all_tress.get(self.to_key(index_root + 1, end), [None])
                         for left_tree in left_trees:
                             for right_tree in right_trees:
                                 new_root = TreeNode(index_root)
                                 new_root.left = left_tree
                                 new_root.right = right_tree
                                 all_tress[self.to_key(start, end)].append(new_root)
         return all_tress.get(self.to_key(1, n))
 
     def to_key(self, start, end):
         return str(start) + str(end)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def generateSubTrees(self, left, right):
         ret = []
         if left >= right:
             ret.append(None)
         
         for i in range(left, right):
             left_sub_trees = self.generateSubTrees(left, i)
             right_sub_trees = self.generateSubTrees(i + 1, right)
             
             for left_tree in left_sub_trees:
                 for right_tree in right_sub_trees:
                     root = TreeNode(i)
                     root.left = left_tree
                     root.right = right_tree
                     ret.append(root)
         return ret
     
     def generateTrees(self, n):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         
         if n==0:
             return []
         return self.generateSubTrees(1, n+1)
             

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         def helper(n, start):
             if n < 1:
                 return [None]
             
             res = []
             for i in range(1, n+1):
                 lefts = helper(i-1, start)
                 rights = helper(n-i, start+i)
                 
                 for left in lefts:
                     for right in rights:
                         root = TreeNode(i+start)
                         root.left = left
                         root.right = right
                         res.append(root)
                         
             return res
         
         return helper(n, 0) if n else []
             

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def clone(self,root):
         if root==None: return root
         left=self.clone(root.left)
         temp=TreeNode(self.n)
         self.n+=1
         temp.left=left
         temp.right=self.clone(root.right)
         return temp
         
     def generateTrees(self, n):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if n==0: return []
         mapp={0:[None],1:[TreeNode(0)]}
         
         for i in range(2,n+1):
             mapp[i]=[]
             for l in range(0,i):
                 r=i-l-1
                 for treel in mapp[l]:
                     for treer in mapp[r]:
                         temp=TreeNode(0)
                         temp.left=treel
                         temp.right=treer
                         mapp[i].append(temp)
         ans=[]
         for tree in mapp[n]:
             self.n=1
             temp=self.clone(tree)
             ans.append(temp)
         return ans
                         
                         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def clone(self,root):
         if root==None: return root
         temp=TreeNode(root.val)
         temp.left=self.clone(root.left)
         temp.right=self.clone(root.right)
         return temp
     def populate(self,root):
         if root==None: return
         self.populate(root.left)
         root.val=self.n
         self.n+=1
         self.populate(root.right)
         
     def generateTrees(self, n):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if n==0: return []
         mapp={0:[None],1:[TreeNode(0)]}
         
         for i in range(2,n+1):
             mapp[i]=[]
             for l in range(0,i):
                 r=i-l-1
                 for treel in mapp[l]:
                     for treer in mapp[r]:
                         temp=TreeNode(0)
                         temp.left=treel
                         temp.right=treer
                         mapp[i].append(temp)
         ans=[]
         for tree in mapp[n]:
             self.n=1
             temp=self.clone(tree)
             self.populate(temp)
             ans.append(temp)
         return ans
                         
                         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def clone(self,root):
         if root==None: return root
         temp=TreeNode(root.val)
         temp.left=self.clone(root.left)
         temp.right=self.clone(root.right)
         return temp
     def populate(self,root):
         if root==None: return
         self.populate(root.left)
         root.val=self.n
         self.n+=1
         self.populate(root.right)
         
     def generateTrees(self, n):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if n==0: return []
         mapp={0:[None],1:[TreeNode(0)]}
         
         for i in range(2,n+1):
             mapp[i]=[]
             for l in range(0,i):
                 r=i-l-1
                 for treel in mapp[l]:
                     for treer in mapp[r]:
                         temp=TreeNode(0)
                         temp.left=self.clone(treel)
                         temp.right=self.clone(treer)
                         mapp[i].append(temp)
         
         for tree in mapp[n]:
             self.n=1
             self.populate(tree)
         return mapp[n]
                         
                         

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if not n:
             return []
         return self.generateBST(1,n)
         
     def generateBST(self,start,end):
         res = []
         if start>end:
             res.append(None) 
         for i in range(start,end+1):
             leftlists = self.generateBST(start,i-1)
             rightlists = self.generateBST(i+1,end)
             for left in leftlists:
                 for right in rightlists:
                     root = TreeNode(i)
                     root.left = left
                     root.right = right
                     res.append(root)
         return res 

# 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):
         """
         :type n: int
         :rtype: List[TreeNode]
         """
         if n == 0:
             return []
         rtnList = []
         for i in range(n,0,-1):
             newList = []
             if rtnList == []:
                 newList = [TreeNode(i)]
             else:
                 for t in rtnList:
                     newList += self.insertNode(t, i)
             rtnList = newList
         return rtnList
     
     def insertNode(self, tree, i):
         """
         insert node to the bottom left
         """
         p = tree
         rtnTree = []
         node = TreeNode(i)
         node.right = self.copyTree(tree)
         rtnTree += node,
         while True:
             node = TreeNode(i)
             newTree = self.copyTree(tree)
             newP = newTree
             while newP.val != p.val:
                 newP = newP.left
             node.right = newP.left
             newP.left = node
             rtnTree += newTree,
             if p.left:
                 p = p.left
             else:
                 break
         return rtnTree
         
         
     
     def copyTree(self,tree):
         newTree = None
         if tree:
             newTree = TreeNode(tree.val)
         if tree.left:
             newTree.left = self.copyTree(tree.left)
         if tree.right:
             newTree.right = self.copyTree(tree.right)
         return newTree