题目

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

示例:

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

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

约定：1 <= n <= 19

第一感觉

第一眼看到这个题目，整个人都是懵的。

我是谁？我在哪里？我为什么而来？

无奈之下，只能去看下解析，这里整理下来，便于后续学习。

BST 的概念

很多解法都是直接上 DP 解法，不过我们还是从基础学起。

到底什么是 BST（二叉搜索树）？

其实这个概念非常简单，二叉树里每个节点都是一个爸爸，每个爸爸有两个儿子。

而二叉“搜索”树就是要满足一个额外的条件：所有左儿子的数字都比爸爸数字小，所有右儿子的数字都比爸爸数字大。

例子

至于为什么叫二叉搜索树，实际上和二分查找法是一一对应的。

这种数据结构就是为了提升查询速度而生的，可以保证每次缩短一半的查询范围。

java 如何实现 binary search 二分查找法？

解题思路

由于 1,2…n 这个数列是递增的，所以我们从任意一个位置“提起”这课树，都满足二叉搜索树的这个条件：左边儿子数小于爸爸数，右边儿子数大于爸爸数   从 1,2,…n 数列构建搜索树，实际上只是一个不断细分的过程。

例子

例如，我要用 [1,2,3,4,5,6] 构建

首先，提起 “2” 作为树根，[1]为左子树，[3,4,5,6] 为右子树   现在就变成了一个更小的问题：如何用 [3,4,5,6] 构建搜索树？

比如，我们可以提起 “5” 作为树根，[3,4] 是左子树，[6] 是右子树   现在就变成了一个更更小的问题：如何用 [3,4] 构建搜索树？

那么这里就可以提起 “3” 作为树根，[4] 是右子树；或 “4” 作为树根，[3] 是左子树   可见 n=6 时的问题是可以不断拆分成更小的问题的  

推广

假设 f(n)= 我们有 n 个数字时可以构建几种搜索树

我们可以很容易得知几个简单情况 f(0) = 1, f(1) = 1, f(2) = 2

(注：这里的 f(0) 可以理解为 =1 也可以理解为 =0，这个不重要，我们这里理解为 =1，即没有数字时只有一种情况，就是空的情况）   那 n=3 时呢？

我们来看 [1,2,3]

如果提起 1 作为树根，左边有f(0)种情况，右边 f(2) 种情况，左右搭配一共有 f(0)*f(2) 种情况

如果提起 2 作为树根，左边有f(1)种情况，右边 f(1) 种情况，左右搭配一共有 f(1)*f(1) 种情况

如果提起 3 作为树根，左边有f(2)种情况，右边 f(0) 种情况，左右搭配一共有 f(2)*f(0) 种情况

容易得知 f(3) = f(0)*f(2) + f(1)*f(1) + f(2)*f(0)

ps: 因为左右两边是独立的，所有的情况就是左子树的所有可能*右子树的所有可能。

同理,

f(4) = f(0)*f(3) + f(1)*f(2) + f(2)*f(1) + f(3)*f(0)

f(5) = f(0)*f(4) + f(1)*f(3) + f(2)*f(2) + f(3)*f(1) + f(4)*f(0)

找规律

其实分析到这里，这一题就变成了一道初中数学——找规律。

对于每一个 n，其式子都是有规律的：每一项两个 f() 的数字加起来都等于 n-1。   既然我们已知 f(0)=1, f(1)=1

那么就可以先算出 f(2),再算出 f(3),然后 f(4) 也可以算了…

计算过程中可以把这些存起来，方便随时使用

最后得到的 f(n) 就是我们需要的解了。

代码实现

java

实际上这题本质上还是一道 DP 问题。

public int numTrees(int n) {
    int[] dp = new int[n+1];
    // 初始化
    dp[0] = 1;
    dp[1] = 1;
    // 遍历
    for(int i = 2; i <= n; i++) {
        int sum = 0;
        for(int j = 0; j < i; j++) {
            // 左边 * 右边
            sum += dp[j] * dp[i-1-j];
        }
        dp[i] =sum ;
    }
    return dp[n];
}

效果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Binary Search Trees.
Memory Usage: 35.8 MB, less than 39.07% of Java online submissions for Unique Binary Search Trees.

复杂度分析

时间复杂度：O(N^2) N 个数据，每一个节点有需要继续遍历 N 次。

空间复杂度： O(N)

数学的解法

还能更优吗？

一般而言，我们超越了 100% 的答案，也算是通过了。

不过如果要求是最优解的话，上面的答案，显然是远远不够的。

卡塔兰数 C_n

事实上我们在方法一中推导出的 G(n)函数的值在数学上被称为卡塔兰数 C_n。

卡塔兰数更便于计算的定义如下:

C_0 = 1;

C_n+1 = (2(2n+1) / n+2 ) * C_n

java 实现

那么上面的代码就可以如下实现：

public int numTrees(int n) {
    // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
    long c = 1;
    // 当然，针对 2 的乘法，还可以使用位运算进行优化。
    for (int i = 0; i < n; ++i) {
        c = c * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) c;
}

效果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Binary Search Trees.
Memory Usage: 35.7 MB, less than 52.56% of Java online submissions for Unique Binary Search Trees.

复杂度分析

时间复杂度 : O(n)，其中 nn 表示二叉搜索树的节点个数。我们只需要循环遍历一次即可。

空间复杂度 : O(1)。我们只需要常数空间存放若干变量。

所以说，学好数学是多么的重要！

优化的尽头

问

那么问你，这就是最优解了吗？

只针对这一题，你还有更快的解法吗？

面向测试案例编程

这里要介绍一种非常赖皮，但是很有用的解法，那就是面向测试案例编程。

题目中 n 的数量实际上是固定的，所以答案是可以枚举的。

本质上就是我们先给出上面的算法，然后提前结算出所有的答案，然后利用查表法，节省计算的时间。

java 实现

int numTrees(int n) {
    switch(n){
        case 1: return 1;
        case 2: return 2;
        case 3: return 5;
        case 4: return 14;
        case 5: return 42;
        case 6: return 132;
        case 7: return 429;
        case 8: return 1430;
        case 9: return 4862;
        case 10: return 16796;
        case 11: return 58786;
        case 12: return 208012;
        case 13: return 742900;
        case 14: return 2674440;
        case 15: return 9694845;
        case 16: return 35357670;
        case 17: return 129644790;
        case 18: return 477638700;
        case 19: return 1767263190;
        default: return 0;
    }
}

效果：

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Binary Search Trees.
Memory Usage: 35.4 MB, less than 90.45% of Java online submissions for Unique Binary Search Trees.

当然，严格而言，这已经不是算法了，所以实际面试过程中，一定要先给出前面的解法，最后给出这个解法。

也算是多出一种解题思路。

小结

希望本文对你有帮助，如果有其他想法的话，也可以评论区和大家分享哦。

各位极客的点赞收藏转发，是老马持续写作的最大动力！

参考资料

  • 顺序查找

https://www.cnblogs.com/yw09041432/p/5908444.html

https://www.jb51.net/article/53863.htm

https://blog.csdn.net/jiandanokok/article/details/50517837

  • 二分查找

二分搜索算法

https://www.cnblogs.com/ider/archive/2012/04/01/binary_search.html