题解 | NC150二叉树的个数

二叉树的个数

已知一棵节点个数为 的二叉树的中序遍历单调递增, 求该二叉树能有多少种树形, 输出答案对取模

解法1：动态规划

对于N个节点的树，将其分为三个部分看，根节点，左子树和右子树。
我们考虑根节点的取值，可以取1到N，
比如取2的时候，左子树即为一颗有一个节点的树，而右节点为节点个数为N-2的树。
此时方案数为一个节点的树的方案数乘上N-2个节点的树的方案数（乘法原理）。
而对于根节点的不同取值，则进行累加（加法原理）。

这样得到递推式：

对于这个公式，我们可以采用递归的记忆化搜索，或者动态规划。
这里详细讲述动态规划的解法：
当我们需要求解时，都已经求得，这个时候只需要按上面的递推式，逐项相乘并累加即可。

时间复杂度：
空间复杂度：

class Solution {
    const static long long MOD = 1000000007; 
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int numberOfTree(int n) {
        std::vector<long long> arr(n + 1);
        arr[0] = arr[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                arr[i] += arr[j] * arr[i - j - 1] % MOD;
                arr[i] %= MOD;
            }
        }
        return arr.back();
    }
};

解法2：卡特兰数

通过逐项分析，或者根据递推公式发现这是卡特兰数，可以将递推公式简化为：

根据该公式，可以在时间复杂度内解决问题。

但是这里因为结果非常大，所以题目要求将结果对取模。
因为题目中涉及除法，所以需要引入逆元：
我们记逆元为，则其满足

而求取逆元的方式有多种：扩展欧几里得，费马小定理和线性递推。
这里考虑到时间复杂度，选择单次求解逆元时间复杂度为，空间复杂度为的线性递推。
时间复杂度：
空间复杂度：

class Solution {
    const static long long MOD = 1000000007; 
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    int numberOfTree(int n) {
        std::vector<long long> arr(n + 1), inv(n + 2);
        arr[0] = arr[1] = 1;
        inv[1] = 1;
        inv[2] = MOD - MOD / 2;
        for (int i = 2; i <= n; ++i) {
            inv[i + 1] = (MOD - MOD / (i + 1)) * inv[MOD % (i + 1)] % MOD;
            arr[i] = arr[i - 1] * (4 * i - 2) % MOD * inv[i + 1] % MOD;
        }
        return arr.back();
    }
};