[数据结构与算法]leetcode96. 不同的二叉搜索树(mid)

题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

解题思路

官方题解

• 动态规划
• 数学结论

代码(动态规划)

	public int numTrees(int n) {
        //g[i]: 表示表示长度为n的序列能构成的不同二叉搜索树的个数
        int[] g = new int[n + 1];
        //g[0]:空树,g[1]只有一个序列构成二叉搜索树的个数
        g[0] = 1;
        g[1] = 1;

        for (int i = 2; i <= n; ++i) {
            //计算f(j, i) = G[j - 1] * G[i - j);
            for (int j = 1; j <= i; ++j) {
                g[i] += g[j - 1] * g[i - j];
            }
        }

        return g[n];
    }

复杂度

代码(数学)

`public int numTrees(int n) {
        // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
        long C = 1;
        for (int i = 0; i < n; ++i) {
            C = C * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) C;
    }

复杂度