c++给出一数字 n，计算包含n个节点的二叉树数目有多少个。

对于包含 n 个节点的二叉树，我们可以将其划分成由一个根节点、左子树和右子树组成的三个部分。假设左子树有 i 个节点，右子树有 n-1-i 个节点，则可以通过左子树和右子树的组合方式得到包含 n 个节点的二叉树。

因此，我们可以通过枚举左子树节点数来计算包含 n 个节点的二叉树数目。设 f(n) 表示包含 n 个节点的二叉树数目，则可以得到递推公式：

f(n) = ∑(f(i) * f(n-1-i)), i = 0 ~ n-1

初始状态为 f(0) = 1，因为空树也算一棵二叉树。

下面是C++代码实现：

#include <iostream>
#include <vector>

using namespace std;

int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    return dp[n];
}

int main() {
    int n;
    cin >> n;
    cout << numTrees(n) << endl;
    return 0;
}

时间复杂度为 O(n^2)，空间复杂度为 O(n)。