Shouyu

Appearance

不同的二叉搜索树 ​

题目描述 ​

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

示例 1：

img

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

题目链接：https://leetcode.cn/problems/unique-binary-search-trees

文章讲解：https://programmercarl.com/0096.不同的二叉搜索树.html

思路 ​

要求二叉搜索树的种类，可以从小n入手。

n=0，空树，0种

n=1，种

n=2，两种

96.不同的二叉搜索树

示例就是n=3的情况。

可以发现元素只有1个，种数1，元素两个，种数2。

元素有3个的话不妨先拆分出一个，剩下两个元素就一定是两种。

拆的话怎么拆？

从示例上看，先拆1，这个1放哪个位置呢？必须放一个固定的位置才好分类，后面还要试着拆2和3，所以就放到根节点。

1根节点，2和3两种元素，种数2；

2根节点，1和3只能放在两侧，种数1；

3根节点，1和2两种元素，种数2；

进一步：

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

动规五部曲 ​

1、dp数组及下标含义 ​

dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。

2.、递推公式 ​

核心划分思想（选根分治）

  • 对于 1..n 中任意一个 j 作为根：
    • 左子树必须由 1..(j-1) 构成，合法 BST 的数量是 dp[j-1]
    • 右子树必须由 (j+1)..n 构成，数量是 dp[n-j]
    • 根固定为 j 时，总数 = dp[j-1] × dp[n-j]
  • 把 j 从 1..n 累加，即 dp[n] = Σ dp[j-1] × dp[n-j]
C++
dp[i] += dp[j-1] * dp[i-j];
3、dp数组初始化 ​
  • dp[0] = 1：空树是一种合法结构（为组合计数的乘法单位1），它保证当 j=1 时左子树 dp[0] 有意义、当 j=n 时右子树 dp[0] 有意义。
  • 代码已设置 dp[0] = 1，并自底向上填表：
    • 外层 i = 1..n 表示节点总数
    • 内层 j = 1..i 表示以 j 为根的划分
    • 转移 dp[i] += dp[j-1] * dp[i-j]
C++
dp[0] = 1
4、确定遍历顺序 ​

节点数 i 的状态是依靠 i 之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态，用j来遍历。

C++
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j];
    }
}
5、举例推导 ​

下标：0 1 2 3 4 5

dp：1 1 2 5 14 42

代码实现 ​

C++
int numTrees(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;                         // 0个节点，一种情况（空树）
    for (int i = 1; i <= n; i++) {     // 遍历节点数 i
        for (int j = 1; j <= i; j++) { // 遍历以 j 为根节点的情况
            // 当 j 为根节点时，左子树有 j-1 个节点，右子树有 i-j 个节点
            // 结果是左子树数量 * 右子树数量，并累加到 dp[i]
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }
    for(int i = 0;i < dp.size();i++){
        std::cout << dp[i] << " ";
    }
    return dp.back();
}