受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数目为BSTn，则有 BSTn=∑BSTk∗BSTn−1−k , 那么BSTn 是卡特兰数，其通项公式是 hn=Cn2n/(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))
蠡口95. Unique Binary Search Trees II
原文：https://www.cnblogs.com/Leisgo/p/11697692.html