leetcode:不同的二叉搜索树

给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]

1.  二叉搜索树：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
2. 求二叉搜索树的个数是卡特兰问题，

因为空树也是一种二叉搜索树，我们将n = 0时赋值为1。

n = 1 时的情况可以看做是其左子树个数乘以右子树的个数，左右子树都是空树，所以1乘1还是1。

n = 2 时，由于1和2都可以为根，分别算出来，再把它们加起来即可。

我们用dp[i]表示当有i个数字能组成的 BST的个数，则 n = 2时的计算表达式可以表示如下：

dp[2] = dp[0] * dp[1]　　　(1为根的情况，因为是二叉搜索树，则左子树一定不存在，右子树可以有一个数字)

　　　　+ dp[1] * dp[0]　　 (2为根的情况，因为是二叉搜索树，则左子树可以有一个数字，右子树一定不存在)

n = 3 时，由于1、2和3都可以为根，根据上面的推导，我们知道二叉搜索树排列个数会由以n个不同数为根时各种情况下剩下的n-1个数所可能的子树排列情况累加而成，在计算这种排列情况时要借助二叉搜索树有序的性质，由此可以写出 n = 3时的计算表达式：

dp[3] = dp[0] * dp[2]　　　(1为根的情况，则左子树一定不存在，右子树可以有两个数字)

　　　　+ dp[1] * dp[1]　　 (2为根的情况，则左右子树都可以各有一个数字)

　　　 + dp[2] * dp[0]　　 (3为根的情况，则左子树可以有两个数字，右子树一定不存在)

　　3.  针对本题，根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1 \ldots i-1][1…i−1]，右子树的节点值的集合为 [i+1 \ldots n][i+1…n]。而左子树和右子　树的生成相较于原问题是一个序列长度缩小的子问题，因此可以用用递归的方法来解决这道题目。

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        ‘‘‘#返回二叉搜索树个数：卡特兰数
        dp=[0]*(n+1)  #dp[i]表示当有i个数字能组成的 BST的个数
        dp[0],dp[1]=1,1
        for i in range(2,n+1):
            for k in range(i):
                dp[i]+=dp[k]*dp[i-k-1]
        return dp[n]‘‘‘
        def generateTrees(start,end):
            if start>end:
                return [None]  #这里很重要，递归的出口必须写成[None]，返回空节点
            Tree=[]
            for i in range(start,end+1):
                leftTree=generateTrees(start,i-1)
                rightTree=generateTrees(i+1,end)
                for l in leftTree:
                    for r in rightTree:
                        curTree=TreeNode(i)
                        curTree.left=l
                        curTree.right=r
                        #print(l)
                        Tree.append(curTree)   
            return Tree
        return generateTrees(1,n) if n else []   #如果输入为空则返回[]

leetcode:不同的二叉搜索树

原文：https://www.cnblogs.com/mmsun/p/13357728.html