目录

• 题目：96. 不同的二叉搜索树
• 前置知识
• 二叉搜索树
• 笛卡尔积
• 方法一：动态规划（DP）

题目：96. 不同的二叉搜索树

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

示例:

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

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

前置知识

二叉搜索树

百度百科（点击直接跳转）https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fr=aladdin

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

笛卡尔积

百度百科（点击直接跳转）https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E4%B9%98%E7%A7%AF/6323173?fromtitle=%E7%AC%9B%E5%8D%A1%E5%B0%94%E7%A7%AF&fromid=1434391&fr=aladdin

笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尔积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

以集合举例
笛卡尔积的符号化为：
A×B={(x,y)|x∈A∧y∈B}
例如，A={a,b}, B={0,1,2}，则
A×B={(a, 0), (a, 1), (a, 2), (b, 0), (b, 1), (b, 2)}
B×A={(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)}

方法一：动态规划（DP）

以下部分转载自力扣官方讲解，极其推荐大家看力扣官方讲解，又细又好
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/
来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路
给定一个有序序列 1⋯n，为了构建出一棵二叉搜索树，我们可以遍历每个数字 ii，将该数字作为树根，将 1⋯(i−1) 序列作为左子树，将 (i+1)⋯n 序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。

在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。

由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。

算法

• 最终结果：G(n) 长度为 n 的序列能构成的不同二叉搜索树的个数。

• F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。

1. G(n)= ∑ i = 1 n F ( i , n ) \sum\limits_{i=1}^nF(i,n) i=1∑n​F(i,n) （1）
2. F(i,n)=G(i−1)⋅G(n−i) （2）
   将公式 (1)，(2) 结合，可以得到 G(n) 的递归表达式：
3. G(n)= ∑ i = 1 n G ( i − 1 ) ⋅ G ( n − i ) \sum\limits_{i=1}^nG(i−1)⋅G(n−i) i=1∑n​G(i−1)⋅G(n−i) (3)

代码

class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

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

复杂度分析

• 时间复杂度 : O( n 2 n^2 n2 ) ，其中 n 表示二叉搜索树的节点个数。G(n)函数一共有 n 个值需要求解，每次求解需要 O(n)的时间复杂度，因此总时间复杂度为 O( n 2 n^2 n2 )

• 空间复杂度 : O(n)。我们需要 O(n)的空间存储 G 数组。