荐 Java刷题笔记15：不同的二叉搜索树（ Unique Binary Search Trees）

题目描述

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

Given n, how many structurally
unique BST’s (binary search trees) that store values 1 … n?

示例 Example

题目链接

本篇文章将给出两种解法。

递归1.0

在本题中，要求以{0,…,n}构成二叉搜索树。二叉搜索树的特点就是对于每一个结点，其左子树的所有元素小于它，右子树所有元素大于它。所以我们可以枚举序列中的不同元素作为根节点，其左边的元素构成左子树，右边元素构成右子树。如{1,2,3,4,5,6},枚举4作为根节点。那么其左子树由{1,2,3}构成、右子树由{5,6}构成。假设有这么一个函数fun1(i,n)其返回值是由长度为n的序列,i为根节点的构成不同搜索二叉树的数量,fun2(n)返回值是长度为n的序列构成的不同搜索二叉树的数量。那么从上面的分析来看，fun1(3,6)=fun2(3)*fun2(2);为什么是乘法？这是因为以枚举到的元素作为根节点时，左右子树不同的组合数为它们的笛卡尔积，左右子树组合不同也会导致整棵树不同。
所以我们将以枚举出的元素作为根节点所计算出的结果累加起来，就得到了最终的结果

 public static int numTrees(int n) {
        //递归
        if (n == 0 || n == 1)
            return 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += numTrees(i) * numTrees(n - i - 1);
        }
        return sum;
}

递归2.0

上面的代码所计算出的结果是正确的，但是时间复杂度很高，因为进行了许多重复的计算，如上面的例子中，当i=0是需要计算numTrees(0)+numTrees(5),继续枚举到i=5时，又需要计算numTrees(5)+numTrees(0);为了利用好已经计算出来的结果，我们可以用一个哈希表将它们储存起来。

 public static int numTrees2(int n) {
        HashMap<Integer, Integer> map = new HashMap<>(n);
        map.put(0, 1);
        map.put(1, 1);
        return help(n, map);
    }

public static int help(int n, HashMap<Integer, Integer> map) {
        if (map.containsKey(n))
            return map.get(n);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int left = help(i, map);
            int right = help(n - i - 1, map);
            sum += left * right;
        }
        map.put(n, sum);
        return sum;
}

如此，递归代码便优化完毕，效率还是很高的。在LeetCode上击败了100%的用户。

数学方法（catalan）

卡塔兰数是组合数学中一个常在各种计数问题中出现的数列一般公式为 C(2n,n)/(n+1).
其实对于数学方法，个人并不推荐在编程时使用，一来是可读性不高，二来是无法体现计算机思维。所以个人认为只需要了解此方法就行，知道可以这么计算。

令h(0)=1,h(1)=1，卡塔兰数满足递归式：
h(n)= h(0)*h(n-1) + h(1)*h(n-2) + … + h(n-1)h(0) (其中n>=2),这是n阶递推关系;
还可以化简为1阶递推关系: 如h(n)=(4n-2)/(n+1)*h(n-1)(n>1) ；h(0)=1
令n=n+1;可得出h(n+1)=(4n+2)/(n+2)*h(n).如此我们便可以从i=0开始计算到i=n。注意在计算机中整数’/'只保存整数部分，所以先计算乘法再计算除法才能得出正确的结果。

  public int numTrees3(int n) {
        long result = 1;
        for (int i = 0; i < n; ++i) {
            result = result * (4 * i + 2) / (i + 2);
        }
        return (int) result;
}

数学方法一般来说效率是最高的，这段代码在执行时间上也击败了100%的LeetCode用户。

本文地址：https://blog.csdn.net/First_C0de/article/details/107353328