程序员代码面试指南 3.23：统计和生成所有不同的二叉树

1、思路

• 在动态规划中，我们用nums[i]来代表i个节点的搜索二叉树有多少种可能；

• 假设一棵二叉搜索树有i个节点，若以j (1 <= j <= i)作为头节点，那么i的左子树有i - 1个节点，右子树有i - j个节点。故以i为头节点的可能结构有nums[i - 1] * nums[i - j]种。

2、代码

#include <iostream>
#include <vector>

using namespace std;

int numTrees(int n)
{
    if (n < 2)
    {
        return 1;
    }

    vector<long long> nums(n + 1, 0);
    nums[0] = 1;                        //初始化 0 个节点有 1 中可能结构

    for (int i = 1; i <= n; ++ i)       //二叉搜索树有 i 个节点
    {
        for (int j = 1; j <= i; ++ j)   //以 j 为头节点
        {
            nums[i] = ((nums[j - 1] * nums[i - j] % 1000000007) + nums[i]) % 1000000007;
        }
    }

    return nums[n];
}

int main()
{
    int n;
    cin >> n;

    cout << numTrees(n) << endl;

    return 0;
}