96.不同的二叉搜索树

一、题目描述

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

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

二、题解

1. 应用卡塔兰数

• 卡特兰数的通项式：$A_{n}=\frac{1}{n+1} C_{2 n}^{n}=C_{2 n}^{n}-C_{2 n}^{n-1}$

• 卡特兰数的递推式：$A_{n+1}=\sum_{i=0}^{n} a A_{i} A_{n-i}$

因为通项式中的数太大会造成，所以采用递推式进行计算

2.代码

int numTrees(int n)
{
    long res = 1;
    for (int i = 0; i < n; ++i)
        res = res * 2 * (2 * i + 1) / (i + 2);
    return res;
}