二叉树的个数

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-07-26

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
#define MOD_VAL 1000000007
long long my_fact(long long end_val, long long start_val)
{
    long long res = 1;
    while(start_val <= end_val)
        res = res*start_val++ % MOD_VAL;
    return res;
}
long long binaryPow(long long base, int exponent)
{
    long long res = 1;
    while(exponent)
    {
        if(exponent & 1) res = res*base % MOD_VAL;
        base = base*base % MOD_VAL;
        exponent >>= 1;
    }
    return res;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算二叉树个数
 * @param n int整型 二叉树结点个数
 * @return int整型
 */
int numberOfTree(int n ) {
    // write code here
    return my_fact(n<<1, n+2)*binaryPow(my_fact(n, 2), MOD_VAL-2) % MOD_VAL;
}
};

C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2021-10-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int mod=1e9+7;
    long long power(long long a,long long b){
        long long res=1;
        while(b){
            if(b&1)res=res*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return res;
    }
    long long inv(long long x){
        return power(x,mod-2);
    }
    int numberOfTree(int n) {
        if (n >= 3000) return -1;
        // write code here
        long long res=1;
        for(int i=2;i<=n;i++){
            res=res*(4*i-2)%mod*inv(i+1)%mod;
        }
        return res;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-05-08

class Solution {
  public:

#define MOD_VAL 1000000007
    long long my_fact(long long end_val, long long start_val) {
        long long z = 1;
        while (start_val <= end_val)
            z = z * start_val++ % MOD_VAL;
        return z;
    }
    long long binaryPow(long long base, int exponent) {
        long long z = 1;
        while (exponent) {
            if (exponent & 1)
                z = z * base % MOD_VAL;
            base = base * base % MOD_VAL;
            exponent >>= 1;
        }
        return z;
    }
    int numberOfTree(int n ) {
        return my_fact(n << 1, n + 2) * binaryPow(my_fact(n, 2), MOD_VAL - 2) % MOD_VAL;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2021-08-03

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int mod=1e9+7;
    long long power(long long a,long long b){
        long long res=1;
        while(b){
            if(b&1)res=res*a%mod;
            b>>=1;
            a=a*a%mod;
        }
        return res;
    }
    long long inv(long long x){
        return power(x,mod-2);
    }
    int numberOfTree(int n) {
        // write code here
        long long res=1;
        for(int i=2;i<=n;i++){
            res=res*(4*i-2)%mod*inv(i+1)%mod;
        }
        return res;
    }
};

C 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2021-07-17

#define MOD_VAL 1000000007
long long my_fact(long long end_val, long long start_val)
{
    long long res = 1;
    while(start_val <= end_val)
        res = res*start_val++ % MOD_VAL;
    return res;
}
long long binaryPow(long long base, int exponent)
{
    long long res = 1;
    while(exponent)
    {
        if(exponent & 1) res = res*base % MOD_VAL;
        base = base*base % MOD_VAL;
        exponent >>= 1;
    }
    return res;
}
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 计算二叉树个数
 * @param n int整型 二叉树结点个数
 * @return int整型
 */
int numberOfTree(int n ) {
    // write code here
    return my_fact(n<<1, n+2)*binaryPow(my_fact(n, 2), MOD_VAL-2) % MOD_VAL;
}

详情