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

For example,

Given n = 3, your program should return all 5 unique BST's shown below.

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

使用cache缓存时间和空间复杂度都是O(n^2)?

有了上一题给定值求解不同二叉搜索树个数的题目，则自然而然引出了现在这题，求解所有的不同二叉搜索树。

根据Unique Binary Search Trees的分析可知，给出一个1...n的范围，可行的二叉搜索树的数目是卡特兰数，不是一个n的多项式的值。所以这道题要求给出所有不同二叉树，自然也不是多项式时间可以解决的。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（注意得出n1个左子树的情况，n2个右子树的情况后，得出所有不同的树遵循乘法原则，即有n1*n2种选择，具体代码中表现为2 层循环），构造好之后作为当前树的结果返回。代码如下：

class Solution(object):    def generateTrees(self, n):        """        :type n: int        :rtype: List[TreeNode]        """        if not n:            return []        return self.helper(1,n)            def helper(self,min,max):        if min>max:            return [None]        res = []        for i in range(min,max+1):            leftSubTree = self.helper(min,i-1)            rightSubTree = self.helper(i+1,max)            for j in leftSubTree:                for k in rightSubTree:                    root = TreeNode(i)                    root.left = j                    root.right = k                     res.append(root)        return res

注意leetcode在N为0时给出的结果为［］，但是实际在左子树或者右子树为空的情况需要用None来表示，为了表示所有左子树，左子树的情况，用list来进行存储。算法的时间复杂度为非常数时间，空间复杂度也是。如果选择自底向上，则需要存储大量的节点，不是好的选择。

 该题在循环中递归调用求解的思路在其他的问题中也有出现，值得掌握。