安徽省住房和城乡建设厅门户网站,如何做网站与网页,黄骅市海边,linux服务器安装网站力扣第96题 - 不同的二叉搜索树 题目描述
给定一个整数 n#xff0c;求以 1 到 n 为节点组成的所有 不同的二叉搜索树#xff08;BST#xff09; 的个数。 题目分析
二叉搜索树的性质
对于一个二叉搜索树#xff0c;以 i 为根节点#xff1a; 左子树的节点值来自 [1, i…力扣第96题 - 不同的二叉搜索树 题目描述
给定一个整数 n求以 1 到 n 为节点组成的所有 不同的二叉搜索树BST 的个数。 题目分析
二叉搜索树的性质
对于一个二叉搜索树以 i 为根节点 左子树的节点值来自 [1, i-1]。右子树的节点值来自 [i1, n]。 左右子树分别是独立的子问题即左右子树的结构不会相互影响。
解法思路
本题的核心在于使用 动态规划 或 卡特兰数公式 进行求解。 解法1动态规划
定义状态
设 dp[i] 表示由 i 个节点组成的不同 BST 的个数。
状态转移方程
当以 j 为根节点时 左子树有 j-1 个节点右子树有 i-j 个节点。 所以以 j 为根的 BST 数量为 d p [ j − 1 ] × d p [ i − j ] dp[j-1] \times dp[i-j] dp[j−1]×dp[i−j]将 j 从 1 到 i 遍历累加所有可能的情况 d p [ i ] ∑ j 1 i d p [ j − 1 ] × d p [ i − j ] dp[i] \sum_{j1}^{i} dp[j-1] \times dp[i-j] dp[i]∑j1idp[j−1]×dp[i−j]
初始化
dp[0] 1空树是一种有效的 BST。dp[1] 1只有一个节点的树只有一种结构。
实现步骤
创建数组 dp大小为 n1。初始化 dp[0] 和 dp[1]。从 2 到 n 遍历计算每个 dp[i]。最后返回 dp[n]。 C语言实现动态规划
#include stdio.h
#include stdlib.hint 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 ) O(n^2) O(n2)。 空间复杂度 动态规划数组 dp 的大小为 O ( n ) O(n) O(n)。 解法2卡特兰数公式
公式推导
二叉搜索树的数量满足卡特兰数定义 C n 1 n 1 ( 2 n n ) C_n \frac{1}{n1} \binom{2n}{n} Cnn11(n2n) C n C_n Cn 是第 n 个卡特兰数。它表示从 1 到 n 的节点所组成的不同 BST 的个数。
实现步骤
使用卡特兰数的公式直接计算 C n ( 2 n ) ! ( n 1 ) ! ⋅ n ! C_n \frac{(2n)!}{(n1)! \cdot n!} Cn(n1)!⋅n!(2n)! 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); // (n1)! * n!return numerator / denominator;
}int main() {int n 5; // 测试输入printf(Number of unique BSTs for n %d: %d\n, n, numTrees(n));return 0;
}复杂度分析 时间复杂度 计算阶乘的时间复杂度为 O ( n ) O(n) O(n)整体复杂度为 O ( n ) O(n) O(n)。 空间复杂度 只使用常数空间复杂度为 O ( 1 ) O(1) O(1)。 示例解析
示例输入
n 3示例输出
Number of unique BSTs for n 3: 5对应的 5 种 BST 是
根节点 1右子树 [2, 3]。根节点 2左子树 [1]右子树 [3]。根节点 3左子树 [1, 2]。根节点 1右子树 [3]中间插入 2。根节点 3左子树 [2]中间插入 1。 总结
动态规划 是解决本题的核心思想通过状态转移方程逐步构造所有可能的 BST 个数。卡特兰数公式 是数学推导的简洁方法适合需要快速计算的场景。动态规划适合理解递归关系公式计算适合处理较大规模的输入。
