LeetCode 96. 不同的二叉搜索树

题目描述

✅ 96. 不同的二叉搜索树

image-20250419000929377

image-20250507213638874

思路分析

这是一个经典的卡特兰数问题，用动态规划解决较为直观。

image-20250507214611036

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13



func numTrees(n int) int {
	// 创建 dp 数组，dp[i] 表示 i 个节点能组成的 BST 数量
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1 // 初始化边界条件

	for i := 2; i <= n; i++ {
		for j := 1; j <= i; j++ {
			// j 作为根节点，左子树有 j-1 个节点，右子树有 i-j 个节点
			dp[i] += dp[j-1] * dp[i-j]
		}
	}
	return dp[n]
}
  • 时间复杂度：O(n²)，双重循环构建 dp 数组。
  • 空间复杂度：O(n)，使用一个长度为 n+1 的 dp 数组。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/69678908
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！