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

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

题目描述

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

题目分析

二叉搜索树的性质

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

解法思路

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

解法1：动态规划

定义状态

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

状态转移方程

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

初始化

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

实现步骤

创建数组 dp，大小为 n+1。
初始化 dp[0] 和 dp[1]。
从 2 到 n 遍历计算每个 dp[i]。
最后返回 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;
}

复杂度分析

时间复杂度：
- 双层循环：外层从 2 到 n，内层从 1 到 i。
- 总体复杂度为 $O(n^2)$ 。
空间复杂度：
- 动态规划数组 dp 的大小为 $O (n)$ 。

解法2：卡特兰数公式

公式推导

二叉搜索树的数量满足卡特兰数定义：
$C_n = \frac{1}{n+1} \binom{2n}{n}$

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

实现步骤

使用卡特兰数的公式直接计算：
$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;
}