96. 不同的二叉搜索树

曾经终败给现在 2023-02-26 09:23 111阅读 0赞

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

示例:

在这里插入图片描述

来源：力扣（LeetCode）添加链接描述

我的代码：

class Solution {
public:
    int numTrees(int n) {
        int dp[n+1];
        if(n == 1) return 1;
        if(n == 2) return 2;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = 0;
            for(int j = 1; j <= i/2; j++){
                dp[i] += dp[i-j]*dp[j-1]*2;
            }
            if(i % 2 == 1) dp[i] += dp[i/2]*dp[i/2];
        }
        return dp[n];
    }
};

官方题解：
动态规划：

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                G[i] += G[j - 1] * G[i - j];
            }
        }
        return G[n];
    }
};

卡特兰数：
在这里插入图片描述

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 (int)C;
    }
};