96. 不同的二叉搜索树

考点

• 区间DP

思路

一、问题描述

给定一个正整数 \(n\)，表示有 \(n\) 个互不相同的节点，其值分别为 \(1,2,\dots,n\)。 要求计算：使用这些节点可以构造出多少种不同结构的二叉搜索树（BST）。

二叉搜索树满足以下性质：

• 左子树所有节点的值 小于 根节点
• 右子树所有节点的值 大于 根节点
• 左右子树本身也都是二叉搜索树

本题只关心结构数量，不要求构造具体的树。

---

二、问题建模

1. 建模思路

二叉搜索树的一个关键特性是：

树的结构只与“节点数量”有关，而与节点的具体取值无关。

例如，使用节点集合 \(\{1,2,3\}\) 和 \(\{5,6,7\}\) 能构造出的 BST 数量是相同的。

因此，可以将问题抽象为：

给定 \(n\) 个节点，求能构造出的不同 BST 的数量。

---

2. 状态定义

定义一维动态规划数组： \[ f[i] = \text{使用 } i \text{ 个节点可以构造的不同 BST 的数量} \] 这是一个计数型 DP，状态只与节点个数有关，不涉及具体区间。

---

3. 状态划分（核心建模）

考虑如何从较小规模的子问题组合出 \(f[i]\)。

对于 \(i\) 个节点：

• 枚举其中某一个节点作为根节点
• 假设第 \(j\) 个节点作为根（\(1 \le j \le i\)）
  • 左子树有 \(j-1\) 个节点
  • 右子树有 \(i-j\) 个节点

根据二叉搜索树的性质：

• 左右子树可以独立构造
• 左子树结构数为 \(f[j-1]\)
• 右子树结构数为 \(f[i-j]\)

当根节点固定为 \(j\) 时，可构造的 BST 数量为： \[ f[j-1] \times f[i-j] \]

---

三、状态转移方程

将所有可能的根节点情况累加，得到状态转移方程： \[ \boxed{ f[i] = \sum_{j=1}^{i} f[j-1] \times f[i-j] } \]

---

1. 边界条件

• \(f[0] = 1\)

含义： 空树也被视为一种合法的 BST，这在组合计数中是必要的，否则转移方程将无法成立。

---

2. 初始化与计算顺序

• 从小到大计算 \(f[1], f[2], \dots, f[n]\)
• 每个 \(f[i]\) 都只依赖于更小的状态，满足 DP 的无后效性

---

四、算法复杂度分析

• 时间复杂度： \[ O(n^2) \] 外层枚举节点数 \(i\)，内层枚举根节点 \(j\)

• 空间复杂度： \[ O(n) \] 仅使用一维 DP 数组

---

五、算法本质说明

上述递推关系正是卡特兰数（Catalan Number）的经典定义之一： \[ C_n = \sum_{k=0}^{n-1} C_k \times C_{n-1-k} \] 本题的答案即为第 \(n\) 个卡特兰数。 因此，这道题在算法竞赛和面试中常被视为Catalan 数的模板题。

---

六、AC代码

class Solution {
public:
    int numTrees(int n) {
        // f[i] 表示使用 i 个节点可以构造的不同二叉搜索树数量
        int f[25] = {};

        // 边界条件：空树算作 1 种
        f[0] = 1;

        // 枚举节点总数 i
        for (int i = 1; i <= n; ++i) {
            // 枚举根节点的位置 j
            for (int j = 1; j <= i; ++j) {
                // 左子树节点数为 j-1
                // 右子树节点数为 i-j
                // 左右子树组合数相乘并累加
                f[i] += f[j - 1] * f[i - j];
            }
        }

        // 返回使用 n 个节点的结果
        return f[n];
    }
};

---

七、小结

• 本题通过节点数量抽象问题规模，避免了区间 DP 的复杂性
• 核心在于正确理解：
  • 根节点的枚举
  • 左右子树的独立性
• 状态转移方程清晰、对称，是典型的结构计数 DP

这套建模方法在后续的树结构计数、括号匹配、出栈序列等问题中都会反复出现。