Leetcode每日刷题(三)

题目：不同的二叉搜索树

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

示例

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

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

解法一：动态规划

思路：

给定一个有序序列 ,为了构建出一个二叉搜索树，可遍历每个数字 ，将该数字作为树根，将 序列作为左子树，将 作为右子树，接着可按照同样的方法递归构建左子树和右子树。

方案

定义两个函数

1、 长度为 的序列可构成的二叉搜索树个数。
2、 以 为根、序列长度为 的不同二叉搜索树个数 。

易得

对于给定序列 ，我们选择数字作 为根，则根为 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积

即:

由此得出：

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

代码实现如下：

public static int numTrees(int n) {
    int[] ints = new int[n + 1];
    ints[0] = 1;
    ints[1] = 1;

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

• 时间复杂度： ， 表示二叉搜索树的节点个数
• 空间复杂度：

解法二：数学

思路：

解法一中推到出的 函数的值在数学上称为卡塔兰数 。卡塔兰数有以下特性：

即：

public static int numTrees(int n) {
    long c = 1;
    for (int i = 2; i <= n; i++) {
        // 这里不要用 *=, 否则会出现因整除省略小数导致的结果异常
        c = c*2*(2*i - 1)/(i + 1);
    }
    return (int)c;
}

• 时间复杂度： ， 表示二叉搜索树的节点个数
• 空间复杂度：

文章永久链接：https://tech.souyunku.com/26463