受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))