不同的二叉搜索树 - Stellar Observer Protocol

463 字

2 分钟

不同的二叉搜索树

2025-08-18

Algorithms

树

/

二叉树

/

二叉搜索树

/

数学

/

动态规划

题目描述#

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

解题思路#

动态规划核心：
- 定义 dp[i] 表示 i 个节点组成的BST数量
- 递推公式：dp[i] = Σ(dp[j] * dp[i-j-1])，j 为左子树节点数
状态转移原理：
- 枚举每个节点作为根节点
- 左子树节点数 j（0≤j<i），右子树节点数 i-j-1
边界条件：
- dp = 1（空树）
- dp = 1（单节点树）
计算顺序：
- 自底向上计算 dp 到 dp[n]
- 避免重复计算子问题

关键洞察#

独立子树原理：
- 二叉搜索树的左右子树结构相互独立
- 组合数 = 左子树方案 × 右子树方案
卡特兰数特性：
- 该问题是卡特兰数的经典应用
- 解为 C(2n,n)/(n+1)
对称性利用：
- dp[j] 和 dp[i-j-1] 可互换
- 避免重复计算相同规模子问题
空间优化：
- 仅需一维数组存储中间结果
- 无需记录完整树结构

复杂度分析#

指标	说明
时间复杂度	O(n²)：双重循环计算dp数组
空间复杂度	O(n)：存储dp数组

代码实现#

1
/**
2
 * @link {https://leetcode.cn/problems/unique-binary-search-trees/}
3
 * @param {number} n
4
 * @return {number}
5
 */
6
var numTrees = function (n) {
7
  const dp = Array(n + 1).fill(0);
8
  dp[0] = 1;
9
  for (let i = 1; i <= n; i++) {
10
    for (let j = 0; j < i; j++) {
11
      dp[i] += dp[j] * dp[i - 1 - j];
12
    }
13
  }
14
  return dp[n];
15
};