95. Unique Binary Search Trees II

# Medium

不是很懂为什么在helper函数的开头要定义一个空的bst数组? 有点难做，需要再练习来加强。

subTree(start, end) 是在区间[start, end]中找出所有的解法，那么就是移动root，root = [start: end]，返回值是一个叫bst的list，存放所有解法的TreeNode(root)树结构。

用两层循环针对当前的root来构建新的bst

Solution:

1. 由于每次递归时，bst都是新的，因此helper函数的开头新建了一个空bst；

2. root左边有n个解法，root右边有m个解法，那么一共就有n*m个解法，所以一定要用两层嵌套的for循环得到新的bst；

3. helper函数中的终止条件要注意，当start>end时才终止，这时候一定要加上NULL，不然那么多NULL哪里加呢。这一点是最难想清楚的。

First Tab

# 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]:     
        # edge case
        if n == 0:
            return []

        return self.subTree(1, n)
    
    # bst -> List[TreeNode]
    # bst[i] means when (root = i-1), all possible BST
    def subTree(self, start, end): 
        # stop condition
        bst = []
        if start > end:
            bst.append(None)
            return bst
        
        # regular case
        for i in range(start, end+1):
            left = self.subTree(start, i-1)
            right = self.subTree(i+1, end)
            for x in left:
                for y in right:
                    root = TreeNode(i)
                    root.left = x
                    root.right = y
                    bst.append(root)
        return bst

Second Tab

Time complexity: $f_i=\sum(f_{i-1})*\sum(f_{n-i})$ 很难算，空间复杂度是一样的。