96. 不同的二叉搜索树

题目描述

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

示例

思路一：

思路参考：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

给定一个有序序列 1⋯ n1⋯n，为了构建出一棵二叉搜索树，我们可以遍历每个数字 ii，将该数字作为树根，将 1 \cdots (i-1)1⋯(i−1) 序列作为左子树，将 (i+1) \cdots n(i+1)⋯n 序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。

在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。

给定序列 1 ⋯ n1⋯n，我们选择数字 i作为根，则根为 i 的所有二叉搜索树的数量等于左子树能构成的二叉搜索树的数量乘以右子树能构成的二叉搜索树的数量。比如1-7的一个序列，如果以3为根，那以3为根能构成的二叉搜索树的个数为左子树 [1, 2] 能构成的二叉搜索树的数量乘以右子树 [4, 5, 6, 7] 能构成的二叉搜索树的数量。

所以可以借助两个函数，

F(i, n), 表示以 i 为 根节点的 长度为n的序列中能构成的二叉搜索树的个数， 上面的例子中，以3为根能构成的二叉搜索树的个数表示为 F(3, 7)

G(i)表示长度为i的序列能构成的二叉搜索树的个数，容易得出

所以上面 [1, 2] 是长度为2的序列，它能构成的二叉搜索树的数量是 G(2),  [4, 5, 6, 7] 能构成的二叉搜索树的数量 其实和[1, 2, 3, 4]能构成的二叉树搜索树的个数是一样的，所以 [4, 5, 6, 7], 其实是一个长度为4的序列，它能构成的二叉搜索树的数量是 G(4)， 

所以F(3, 7) = G(2) * G(4), 推广， F(i, n) = G(i-1) * G(n-i) ， 所以推出

 1 class Solution {
 2     public int numTrees(int n) {
 3         int[] G = new int[n+1];
 4         G[0] = 1;
 5         G[1] = 1;
 6         for(int i = 2; i <= n; i++){    // 长度为2-n的序列能构成的二叉搜索树的数量
 7             for(int j = 1; j <= i; j++){    // 求出长度为i的序列能构成二叉搜索树的数量
 8                 G[i] += G[j-1] * G[i-j];
 9             }
10         }
11         return G[n];
12     }
13 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：35.7 MB > 17.54%

复杂度分析: 

时间复杂度：很容易看出程序中有两个for循环，所以时间复杂度为O(2n)

空间复杂度：需要一个长度为n+1的临时数组用来存放临时结果， 所以空间复杂度也为O(n)

思路二：卡塔兰数

其实这个公式的计算结果就是卡塔兰数， C₀ = 1, C_n= (2(2n+1)/(n+2))C_n-1, 

所以G(n)其实是可以直接由G(n-1)得到的，所以可以不需要使用一个临时数组，只要一个临时变量存下G(n-1)的结果，就能求出G(n)的结果了

1 class Solution {
2     public int numTrees(int n) {
3         long C = 1;          // 长度为0的序列能构成的二叉搜索树的数量为1
4         for(int i = 0; i < n; i++){    // 长度为1-n的序列能构成的二叉搜索树的数量
5             C = C * 2 * (2*i+1) / (i+2);
6         }
7         return (int)C;
8     }
9 }

leetcode 执行用时：0 ms > 100.00%, 内存消耗：35.7 MB > 17.54%

复杂度分析: 

时间复杂度：很容易看出程序中只有一个for循环，所以时间复杂度为O(n)

空间复杂度：O(1)