力扣第96题 不同的二叉搜索树

力扣第96题 - 不同的二叉搜索树

---

题目描述

给定一个整数 n，求以 1 到 n 为节点组成的所有 不同的二叉搜索树（BST） 的个数。

---

题目分析

二叉搜索树的性质

• 对于一个二叉搜索树，以 i 为根节点：
  • 左子树的节点值来自 [1, i-1]。
  • 右子树的节点值来自 [i+1, n]。
• 左右子树分别是独立的子问题，即：左右子树的结构不会相互影响。

解法思路

本题的核心在于使用 动态规划 或 卡特兰数公式 进行求解。

---

解法1：动态规划

定义状态

设 dp[i] 表示由 i 个节点组成的不同 BST 的个数。

状态转移方程

1. 当以 j 为根节点时：
   • 左子树有 j-1 个节点；
   • 右子树有 i-j 个节点。
2. 所以以 j 为根的 BST 数量为：
   $dp[j-1]\times dp[i-j]$
3. 将 j 从 1 到 i 遍历，累加所有可能的情况：
   $dp[i]={\sum }_{j=1}^{i}dp[j-1]\times dp[i-j]$

初始化

• dp[0] = 1：空树是一种有效的 BST。
• dp[1] = 1：只有一个节点的树只有一种结构。

实现步骤

1. 创建数组 dp，大小为 n+1。
2. 初始化 dp[0] 和 dp[1]。
3. 从 2 到 n 遍历计算每个 dp[i]。
4. 最后返回 dp[n]。

---

C语言实现（动态规划）

#include <stdio.h>
#include <stdlib.h>

int numTrees(int n) {
    // 动态规划数组
    int* dp = (int*)malloc((n + 1) * sizeof(int));
    dp[0] = 1; // 空树
    dp[1] = 1; // 只有一个节点

    // 填充 dp 数组
    for (int i = 2; i <= n; i++) {
        dp[i] = 0;
        for (int j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j];
        }
    }

    int result = dp[n];
    free(dp); // 释放内存
    return result;
}

int main() {
    int n = 5; // 测试输入
    printf("Number of unique BSTs for n = %d: %d\n", n, numTrees(n));
    return 0;
}

---

复杂度分析

1. 时间复杂度：

   • 双层循环：外层从 2 到 n，内层从 1 到 i。
   • 总体复杂度为 $O(n^2)$。

2. 空间复杂度：

   • 动态规划数组 dp 的大小为 $O(n)$。

---

解法2：卡特兰数公式

公式推导

二叉搜索树的数量满足卡特兰数定义：
$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$

• $C_n$ 是第 n 个卡特兰数。
• 它表示从 1 到 n 的节点所组成的不同 BST 的个数。

实现步骤

1. 使用卡特兰数的公式直接计算：
   $C_n=\frac{(2n)!}{(n+1)!\cdot n!}$

---

C语言实现（卡特兰数）

#include <stdio.h>

// 计算阶乘
unsigned long long factorial(int n) {
    unsigned long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

int numTrees(int n) {
    // 卡特兰数公式
    unsigned long long numerator = factorial(2 * n);    // (2n)!
    unsigned long long denominator = factorial(n) * factorial(n + 1); // (n+1)! * n!
    return numerator / denominator;
}

int main() {
    int n = 5; // 测试输入
    printf("Number of unique BSTs for n = %d: %d\n", n, numTrees(n));
    return 0;
}

---

复杂度分析

1. 时间复杂度：

   • 计算阶乘的时间复杂度为 $O(n)$，整体复杂度为 $O(n)$。

2. 空间复杂度：

   • 只使用常数空间，复杂度为 $O(1)$。

---

示例解析

示例输入：

n = 3

示例输出：

Number of unique BSTs for n = 3: 5

对应的 5 种 BST 是：

1. 根节点 1，右子树 [2, 3]。
2. 根节点 2，左子树 [1]，右子树 [3]。
3. 根节点 3，左子树 [1, 2]。
4. 根节点 1，右子树 [3]，中间插入 2。
5. 根节点 3，左子树 [2]，中间插入 1。

---

总结

1. 动态规划 是解决本题的核心思想，通过状态转移方程，逐步构造所有可能的 BST 个数。
2. 卡特兰数公式 是数学推导的简洁方法，适合需要快速计算的场景。
3. 动态规划适合理解递归关系，公式计算适合处理较大规模的输入。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/144338957

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！