Leetcode-96.不同的二叉搜索树

发表于 分类于 阅读次数：

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

解法1：动态规划

G(n)表示长度为n的序列的不同二叉搜索树的个数

F(i,n)表示以i为根的不同二叉搜索树个数(1<=i<=n)

首先，根据95题的思路，不同的二叉搜索树的个数G(n),是对遍历所有i的F(i,n)之和。即:

G(n)=∑F(i,n)

特别的对于边界情况,G(0)=G(1)=1;

F(i,n)的是左右子树的笛卡尔积。

举例：F(3,7)是以3为根，总共7个节点的二叉搜索树。为了以3为根，左子树要以[1,2]序列建树，右子树要以[4,5,6,7]序列建树，然后让他们组合。巧妙之处[1,2]可以用G(2)表示，[4,5,6,7]可以用G(4)表示，因为G(n)和序列内容无关，只和序列的长度有关。于是F(3,7)=G(2)*G(4)。

也就是F(i,n)=G(i-1)*G(n-i)

结合上面的公式我们可以得到

G(n)=∑G(i-1)*G(n-i)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numTrees(int n) {
        vector<int> g(n+1,0);
        g[0]=1;
        g[1]=1;
        int i,j;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=i;j++)
            {
                g[i]+=g[i-j]*g[j-1];
            }
        }
        return g[n];
    }
};

解法2：数学演绎法

事实上G(n)函数的值被称为卡塔兰数$C_n$,卡塔兰数更便于计算的定义如下：
$$
C_0=1,C_{n+1}=\frac{2(2n+1)}{n+2}C_n
$$
有了上述公式我们能将复杂度变为O(n)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int numTrees(int n) {
        long long c=1;
        for(int i=0;i<n;i++)
        {
            c=c*(2*(2*i+1))/(i+2);
        }
        return c;
    }
};