0096. Unique Binary Search Trees
================================
题目信息
--------
:题号: 0096. 不同的二叉搜索树
:难度: Medium
:主题: 二叉搜索树、动态规划、记忆化搜索、Catalan 数
:原题: `LeetCode 0096 `_
:重点: 从枚举根节点的重复递归,推导到按节点数量计数和 Catalan 递推
题目重述
--------
给定整数 ``n``,计算由数值 ``1..n`` 各使用一次可以构成多少棵结构不同的二叉搜索树。
二叉搜索树要求任意节点左子树中的值都小于该节点,右子树中的值都大于该节点。只需返回树的数量,
不需要构造具体树。
约束为 ``1 <= n <= 19``,答案保证位于 32 位有符号整数范围内。
自建示例
--------
.. code-block:: text
输入:n = 1
输出:1
只有一个节点时,只能构成一棵树。
.. code-block:: text
输入:n = 3
输出:5
以 1、2、3 为根时,左右子树结构数乘积依次为 ``1*2``、``1*1``、``2*1``,总数为 5。
.. code-block:: text
输入:n = 4
输出:14
四个根位置的贡献依次为 ``1*5``、``1*2``、``2*1``、``5*1``。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
long long plainRecursion(int nodes) {
if (nodes <= 1) return 1;
long long total = 0;
for (int leftNodes = 0; leftNodes < nodes; ++leftNodes) {
int rightNodes = nodes - 1 - leftNodes;
total += plainRecursion(leftNodes) *
plainRecursion(rightNodes);
}
return total;
}
long long memoDfs(int nodes, std::vector& memo) {
if (nodes <= 1) return 1;
long long& cached = memo[nodes];
if (cached != -1) return cached;
cached = 0;
for (int leftNodes = 0; leftNodes < nodes; ++leftNodes) {
int rightNodes = nodes - 1 - leftNodes;
cached += memoDfs(leftNodes, memo) *
memoDfs(rightNodes, memo);
}
return cached;
}
int memoizedRecursion(int n) {
std::vector memo(n + 1, -1);
return static_cast(memoDfs(n, memo));
}
int bottomUpDp(int n) {
std::vector count(n + 1);
count[0] = 1;
for (int nodes = 1; nodes <= n; ++nodes) {
for (int leftNodes = 0; leftNodes < nodes; ++leftNodes) {
int rightNodes = nodes - 1 - leftNodes;
count[nodes] += count[leftNodes] * count[rightNodes];
}
}
return static_cast(count[n]);
}
int catalanRecurrence(int n) {
long long value = 1;
for (int k = 0; k < n; ++k) {
value = value * 2 * (2 * k + 1) / (k + 2);
}
return static_cast(value);
}
public:
int numTrees(int n) {
return bottomUpDp(n);
}
};
题解
----
数量状态
~~~~~~~~
对任意 ``nodes`` 个互异且有序的键,BST 的中序遍历顺序已经确定。把一组连续键整体平移,或替换为另一组
保持相对大小关系的键,不会改变可选树形。
因此状态只需记录节点数量:
.. code-block:: text
count[nodes] = 使用 nodes 个有序键能够形成的不同 BST 数量
不需要记录具体值域的起点和终点。
根节点划分
~~~~~~~~~~
在 ``nodes`` 个键中选择排名为 ``leftNodes + 1`` 的键作为根后:
.. code-block:: text
左子树节点数 = leftNodes
右子树节点数 = nodes - 1 - leftNodes
左、右子树可以独立选择结构,所以固定根位置的组合数为两侧数量的乘积。枚举所有根位置得到:
.. code-block:: text
count[nodes] = sum(
count[leftNodes] * count[nodes - 1 - leftNodes]
)
任意非空 BST 都有唯一根位置,并进一步确定唯一的左、右子树结构对,因此各项覆盖全部合法树且互不重复。
空树状态
~~~~~~~~
``count[0] = 1`` 表示一侧为空时存在一种合法选择。叶节点左右都为空,其结构数应为 ``1 * 1``;若空树计数为
0,所有带空子树的合法结构都会被错误消除。
裸递归
~~~~~~
最直接的递归对每种根位置分别递归计算左右节点数。它准确表达了根节点划分,但相同的节点数量会在不同分支中
被反复计算。例如计算 ``count[5]`` 时,``count[2]`` 会从多个根位置重复出现,递归树因此快速膨胀。
记忆化搜索
~~~~~~~~~~
节点数量只有 ``0..n`` 共 ``n+1`` 种。缓存 ``memo[nodes]`` 后,每个数量只完整枚举一次根位置;后续访问
直接返回已有结果。
记忆化保留了自顶向下的推导方式,同时把重复子问题压缩成有限状态。
自底向上
~~~~~~~~
计算 ``count[nodes]`` 时,左右节点数都严格小于 ``nodes``。按节点数从小到大填表即可保证所有依赖已经完成:
.. list-table::
:header-rows: 1
* - 节点数
- 根位置贡献
- 结构数
* - 0
- 空树
- 1
* - 1
- ``1*1``
- 1
* - 2
- ``1*1 + 1*1``
- 2
* - 3
- ``1*2 + 1*1 + 2*1``
- 5
* - 4
- ``1*5 + 1*2 + 2*1 + 5*1``
- 14
公开入口采用该方案,因为状态与 BST 根节点划分直接对应,边界和转移都容易验证。
Catalan 递推
~~~~~~~~~~~~
上述序列正是 Catalan 数,还可以使用相邻项关系:
.. code-block:: text
C(0) = 1
C(k+1) = C(k) * 2 * (2k+1) / (k+2)
它把时间降为 ``O(n)``、额外空间降为 ``O(1)``。整数除法在数学上能够整除,但固定宽整数实现仍需使用足够宽的
中间类型并谨慎安排乘除顺序。动态规划更直接地体现题目的结构来源。
复杂度
~~~~~~
裸递归会重复展开相同节点数量,时间为指数级,递归深度 ``O(n)``。
记忆化搜索和自底向上 DP 都有 ``n`` 个非空状态,每个状态枚举至多 ``n`` 个根位置,时间 ``O(n^2)``,
缓存或数组空间 ``O(n)``。Catalan 相邻项递推时间 ``O(n)``,额外空间 ``O(1)``。