蠡口95. Unique Binary Search Trees II

受LC96. Unique Binary Search Trees的启发，使用递归。包含i...j的BST应该是取好k (i≤k≤j)，之后包含i..(k-1)的BST+k+包含(k+1)..j的BST，如下图所示。

那么包含i...j的所有BST取遍所有看k作为root,从包含i..(k-1)的所有BST取出一个作为root的left，从包含(k+1)..j的所有BST取出一个作为root的right。返回1...n的所有BST即为所求。

时间复杂度分析：假设1~n的所有BST数目为BST，则有 BST=∑BST∗BST那么BST 是卡特兰数，其通项公式是 h=C/(n+1). 推导见这里。

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

class Solution(object):
    def helper(self,i,j):
        if j<i: return([None])
        if i==j: return([TreeNode(i)])
        ans=[]
        for k in range(i,j+1):
            left=self.helper(i,k-1)
            right=self.helper(k+1,j)
            for l in left:
                for r in right:
                    root=TreeNode(k)
                    root.left,root.right=l,r
                    ans.append(root)
        return(ans)

    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n<=0: return([])
        if n==1: return([TreeNode(1)])
        return(self.helper(1,n))