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 \cdots n$，为了构建出一颗二叉搜索树，遍历每个数字 $i$，将 $1 \cdots (i-1)$ 序列作为左子树，将 $(i+1) \cdots n$序列作为右子树，按照同样的方式递归构建左子树和右子树。
在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。
由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。动态规划很适合啦~
算法
题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：

$G(n)$: 长度为 $n$ 的序列能构成的不同二叉搜索树的个数。
$F(i, n)$: 以 $i$ 为根、序列长度为 $n$ 的不同二叉搜索树个数 $(1 \leq i \leq n)$。

可见，$G(n)$ 是我们求解需要的函数。
$G(n)$可以从 $F(i, n)$ 得到，而 $F(i, n)$ 又会递归地依赖于 $G(n)$。
首先，不同的二叉搜索树的总数 $G(n)$，是对遍历所有 $ i (1 \le i \le n)$ 的 $F(i, n)$ 之和。换言之：

$$G(n) = \sum_{i=1}^{n} F(i, n)\qquad \qquad (1)$$

对于边界情况，当序列长度为 $1$（只有根）或为 $0$（空树）时，只有一种情况，即：

$$G(0) = 1, \qquad G(1) = 1$$

给定序列 $1 \cdots n$，我们选择数字 $i$ 作为根，则根为 $i$ 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积(其实就是左子树的种类数乘以右子树的种类数，列举所有的可能性)，对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树，如下图所示：

举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 [1,2,3,4,5,6,7]，我们需要从左子序列 [1,2] 构建左子树，从右子序列 [4,5,6,7] 构建右子树，然后将它们组合（即笛卡尔积）。
公式化：不同二叉搜索树的个数表示为 $F(3, 7)$。我们将 $[1,2]$ 构建不同左子树的数量表示为 $G(2)$, 从 $[4,5,6,7]$ 构建不同右子树的数量表示为 $G(4)$，注意： $G(n)$ 和序列的内容无关，只和序列的长度有关。于是，$F(3,7) = G(2) \cdot G(4)$。 因此，我们可以得到以下公式：

$$F(i, n) = G(i-1) \cdot G(n-i) \qquad \qquad (2)$$

将公式 $(1)$，$(2)$ 结合，可以得到 $G(n)$ 的递归表达式：

$$G(n) = \sum_{i=1}^{n}G(i-1) \cdot G(n-i) \qquad \qquad (3)$$

至此，我们从小到大计算 $G$ 函数即可，因为 $G(n)$ 的值依赖于 $G(0) \cdots G(n-1)$。

代码

class Solution:
	def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0] * (n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]
		return G[n]

复杂度分析

• 时间复杂度 : $O(n^2)$，其中 $n$ 表示二叉搜索树的节点个数。$G(n)$ 函数一共有 $n$ 个值需要求解，每次求解需要 $O(n)$ 的时间复杂度，因此总时间复杂度为 $O(n^2)$。

空间复杂度 : $O(n)$。我们需要 $O(n)$ 的空间存储 $G$ 数组。

方法二：数学

思路与算法
事实上我们在方法一中推导出的 G(n)函数的值在数学上被称为卡塔兰数 C_n。卡塔兰数更便于计算的定义如下:
C_0 = 1, \qquad C_{n+1} = \frac{2(2n+1)}{n+2}C_n
C0=1,Cn+1=n+22(2n+1)Cn
证明过程可以参考上述文献，此处不再赘述。

代码

class Solution(object):
    def numTrees(self, n):
        C = 1
        for i in range(0, n):
            C = C * 2 * (2 * i + 1)/(i+2)
        return int(C)

复杂度分析

时间复杂度 : $O(n)$，其中 $n$ 表示二叉搜索树的节点个数。我们只需要循环遍历一次即可。
空间复杂度 : $O(1)$。我们只需要常数空间存放若干变量。

今天的小菜鸡喝到汤啦~

参考资料

官方题解