LeetCode/96. 不同的二叉搜索树

96. 不同的二叉搜索树

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

示例 ：

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

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

学过数据结构的小伙伴应该都知道，计算n个结点的二叉树的形态数，其实个数就是Catalan数，与其吭哧吭哧一步一步推导动态规划的状态转移方程，不如我们来学习一下Catlan数。

首先我们要知道什么是Catalan数，这里我引用维基百科的定义：

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡塔兰[。有中国学者建议将此数命名为“明安图数”或“明安图-卡塔兰数”。

Catalan的一般项为：

$$C_n = \frac{1}{n+1} \left(\begin{matrix}2n \\ n \end{matrix} \right) = \frac{(2n)!}{(n+1)!n!}$$

Catalan数基于一定的实际意义。在一个n * n的方格中，从(0,0)到(n,n)的路径数，这个路径个数其实就是从2n个路径中挑出n条，所以就是$\left(\begin{matrix}2n \ n \end{matrix} \right)$，但是Catalan还有一定的要求，就是在每次移动过程中不能越过对角线，那么我们就可以得出Catalan数的计算公式$C_n = \left(\begin{matrix}2n \ n \end{matrix} \right)-\left(\begin{matrix}2n \ n+1 \end{matrix} \right)$。

根据维基百科的内容可以知道，Catalan的递推关系为：

$$C_0 = 1 \quad and \quad C_{n+1}=\sum_{i=0}^nC_i C_{n-i} \quad for \quad n \ge 0 \\ C_0 = 1 \quad and \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n$$

这个对应到我们这道题上，令f(i)为以第i个结点为根结点的二叉树的个数，那么有

$$Catalan(n) = f(1)+f(2)...+f(n)$$

其中当i为根结点时，左子树有i-1个结点，右子树有n-i个结点，即$f(i)=Catalan(i-1)*Catalan(n-i)$，这样代入进去，我们就可以得到Catalan数的递推公式了。

具体代码如下：

class Solution {
    public int numTrees(int n) {
        long catalan = 1;   //这里需要用long,否则可能因为数组太大造成结果溢出
        for (int i = 0; i < n; i++) {
            catalan = catalan * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) catalan;
    }
}

本文参考：

1. 维基百科

2. LZM的博客