LeetCode 0096. 不同的二叉搜索树[动态规划详解]

原创

Yano_nankai

修改于 2021-03-19 10:21:17

3900

修改于 2021-03-19 10:21:17

文章被收录于专栏：二进制文集

题目描述

题目链接

给定一个整数 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，为了根据序列构建一棵二叉搜索树。我们可以遍历每个数字 i，将该数字作为树根，1 ... (i-1) 序列将成为左子树，(i+1) ... n 序列将成为右子树。于是，我们可以递归地从子序列构建子树。

在上述方法中，由于根各自不同，每棵二叉树都保证是独特的。

可见，问题可以分解成规模较小的子问题。因此，我们可以存储并复用子问题的解，而不是递归的（也重复的）解决这些子问题，这就是动态规划法。

思考对于数列 1,2,3：

若以 1 为根节点，则数列 2,3 所组成的子树均是 1 的右子树；
若以 2 为根节点，则数列 1 所组成的子树均是 2 的左子树，数列 3 所组成的子树均是 2 的右子树；
若以 3 为根节点，则数列 1,2 所组成的子树均是 3 的左子树。

记数列 1,n，f(n) 为数列 1,n 所组成的二叉搜索树的种类，则：

以 1 为根节点时，其左区间不存在，数量为 0，子树种类为 f(0)；右区间为 2...n，数量为 n - 1，子树种类为 f(n - 1)。则以 1 为根节点的数量为 f(0) * f(n-1)；
以 2 为根节点时，其左区间为1,1，数量为 1，子树种类为 f(1)；右区间为 3,n，数量为 n - 2，子树种类为 f(n - 2)。则以 2 为根节点的数量为 f(1) * f(n-2)；
以 n 为根节点时，其左区间为 1,n-1，数量为 n-1，子树种类为 f(n-1)；右区间不存在，数量为 0，子树种类为 f(0)。则以 n 为根节点的数量为 f(n-1) * f(0)。
一般地，对于 x∈1,n，以 x 为根节点时，其左区间为1,x-1，数量为 x-1，子树种类为 f(x-1)；右区间为 x+1,n，数量为 n - x，子树种类为 f(n - x)。则以 x 为根节点的数量为 f(x - 1) * f(n-x)。

数列 1,n 所组成的二叉搜索树的种类 f(n) 公式为：

f(n) = \sum_{\mathclap{1\le i \le n}} f(i-1)*f(n-i)

其中 f(0) = f(1) = 1。

本题可以新建一个数组 ans，ansi 用于保存 1,i 所组成的二叉搜索树的种类，则可以根据上述公式编写代码。

代码 1

public int numTrees(int n) {
    int[] ans = new int[n + 1];
    ans[0] = 1;
    ans[1] = 1;
    // f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ……
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            ans[i] += ans[j - 1] * ans[i - j];
        }
    }
    return ans[n];
}

复杂度分析：

时间复杂度：其中 i j 进行双重循环，循环次数为 2 + ... + n = (2+n)(n−1)/2，所以时间复杂度是 O(N^2)；
空间复杂度：建立了长度为 n + 1 的数组，所以空间复杂度是 O(N)。

代码 2

其实上述公式就是卡塔兰数，卡塔兰数的通项公式如下：

public int numTrees(int n) {
    // 使用 long 型，int 可能溢出
    long ans = 1;
    for (int i = 0; i < n; i++) {
        ans = ans * 2 * (2 * i + 1) / (i + 2);
    }
    return (int) ans;
}

复杂度分析：

时间复杂度：其中 i j 进行双重循环，循环次数为 2 + ... + n = (2+n)(n−1)/2，所以时间复杂度是 O(N^2)；
空间复杂度：建立了长度为 n + 1 的数组，所以空间复杂度是 O(N)。

代码

class Solution {
    public int numTrees(int n) {
        // 使用 long 型，int 可能溢出
        long ans = 1;
        for (int i = 0; i < n; i++) {
            ans = ans * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) ans;
    }
}