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）
链接：96. Unique Binary Search Trees

解题思路

本题主要考察卡塔兰数，对于非科班出身的本博主肯定是不知道的，不过既然刷到题了正好可以学习一番，这也是刷题的目的。

先来看看n为1，2，3时的情况：

                 1                        n = 1

             2        1                   n = 2
            /          \
           1            2
  
1         3     3      2      1           n = 3
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

因为空树也是一种二叉搜索树，我们将n = 0时赋值为1。

n = 1 时的情况可以看做是其左子树个数乘以右子树的个数，左右子树都是空树，所以1乘1还是1。

n = 2 时，由于1和2都可以为根，分别算出来，再把它们加起来即可。

我们用dp[i]表示当有i个数字能组成的 BST 的个数，则 n = 2时的计算表达式可以表示如下：

dp[2] = dp[0] * dp[1]　　　(1为根的情况，因为是二叉搜索树，则左子树一定不存在，右子树可以有一个数字)

+ dp[1] * dp[0]　　 (2为根的情况，因为是二叉搜索树，则左子树可以有一个数字，右子树一定不存在)

n = 3 时，由于1、2和3都可以为根，根据上面的推导，我们知道二叉搜索树排列个数会由以n个不同数为根时各种情况下剩下的n-1个数所可能的子树排列情况累加而成，在计算这种排列情况时要借助二叉搜索树有序的性质，由此可以写出 n = 3时的计算表达式：

dp[3] = dp[0] * dp[2]　　　(1为根的情况，则左子树一定不存在，右子树可以有两个数字)

+ dp[1] * dp[1]　　 (2为根的情况，则左右子树都可以各有一个数字)

+ dp[2] * dp[0]　　 (3为根的情况，则左子树可以有两个数字，右子树一定不存在)

由此，我们可以得到卡塔兰数列的递推表达式：

C_0=1\,\,\, and \,\,\, C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i} \,\,\,for\,\,n\geq 0 \tag{1} \label{1}

根据以上递推表达式，代码写起来还是比较容易的，具体见解法一。

需要特别注意的是，在C语言当中，数组在声明以后一定要初始化，不然会发生内存泄露。比如下面的代码在运行以后就会报错：

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

}

因为一开始定义好dp数组以后未对其全部数据进行初始化，后面会有溢出，提示如下：

Line 19: Char 28: runtime error: signed integer overflow: 1102416565 * 208363263347 cannot be represented in type 'long int' (solution.c)

另外，由卡特兰数的递推式还可以推导出其通项公式，即 C(2n,n)/(n+1)，表示在 2n 个数字中任取n个数的方法再除以 n+1，为了防止数据溢出，需要将结果result定义为long，具体代见解法二。

代码

解法一

int numTrees(int n){
  
    //数组空间分配及初始化
    int *dp = malloc((n + 1) * sizeof(int));
    memset(dp, 0, (n + 1) * sizeof(int));
    
    dp[0] = dp[1] = 1;
    
    for(int i = 2; i <= n; i++){
        for(int j = 1; j <= i; j++){
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    
    int result = dp[n];
    //释放空间，良好的习惯
    free(dp);
    
    return result;

}

解法二

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

参考

• [LeetCode] 96. Unique Binary Search Trees 独一无二的二叉搜索树