【卡特兰数】不同的二叉搜索树
文章目录
- 96. 不同的二叉搜索树
- 解法一：动态规划
- 状态表示
- 状态转移方程
- 初始化
- 遍历顺序
- 返回值
- 💥解法二：卡特兰数
96. 不同的二叉搜索树
96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
解法一：动态规划
状态表示
一般这类动态规划，找状态表示比较难，都是通过 “举例 + 抽象出相同的子问题” 来表示状态！
比如这里 n = 3 的情况：
我们分别让 1~n 的每个数依次插入二叉树，可以推断当确定了一个根节点之后，左右字数的节点个数就确定了！此时左右子树又会变成相同的子问题，因此我们可以定义状态表示为：dp[i] 表示当节点数量为 i 时，一共有多少颗 BST！
此时其实就可以将上面的情况划分一下：
难的是如何推导状态转移方程，因为它跟我们之前常见的状态转移方程不是很像。
状态转移方程
对于 dp[i]，表示此时有 i 个节点，那么此时对于所有不同的 BST 来说，我们可以按照以下规则来划分，分成不同的 i 类：
- 以
1元素为根节点的所有BST - 以
2</