欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode算法练习——不同的二叉搜索树

程序员文章站 2022-07-15 12:00:17
...

题目:

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

示例:
leetcode算法练习——不同的二叉搜索树

代码如下:

长度为n的序列的不同二叉搜索树个数C(n)为卡塔兰数。

首先,设长度为nn,数ii作为根时,二叉搜索树的个数为F(i,n)F(i,n)
C(n)C(n)=i=1nF(i,n)\sum^n_{i=1}F(i,n)

当数ii作为根时,11i1i-1i+1i+1nn分别构成ii的左子树和右子树。
11i1i-1构成的左子树数量可以用C(i1)C(i-1)表示,i+1i+1nn构成的右子树数量可以用C(ni)C(n-i)表示。

因为长度为n的序列构成的二叉搜索树的数量只与序列长度有关,与序列里数的大小无关。
F(i,n)F(i,n)=C(i1)C(ni)C(i-1)*C(n-i)

所以C(n)C(n)可以写成C(n)C(n)=i=1nC(i1)C(ni)\sum^n_{i=1}C(i-1)*C(n-i)
这是卡塔兰数的形式。

卡塔兰数还可以写成这种形式:
C(n)=C(n1)(4n2)/(n+1)C(n)=C(n-1)*(4n-2)/(n+1)

特殊情况:C(0)=1C(0)=1C(1)=1C(1)=1

class Solution {
public:
    int numTrees(int n) 
    {
        if (n==0) return 1;
        long C = 1;
        for(int i=1;i<=n;i++)
        {
            C = C*(4*i-2)/(i+1);
        }
        return C;
    }
};

运行结果:

leetcode算法练习——不同的二叉搜索树

相关标签: c++