96. 不同的二叉搜索树

题意

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少

种？返回满足题意的二叉搜索树的种数。

难度

中等

示例

示例 1：

096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91-20231104153837.png

输入：n = 3

输出：5

示例 2：

输入：n = 1

输出：1

分析

关于二叉搜索树，上一题我们就讲过了，相信大家还有印象。上一题是求具体方案，这一

题是求方案的个数。

我们可以沿用上一题的思路。

假设 n 个节点的 二叉搜索树 的个数为$ G(n) ， 设 f(i) 为 以 i $为根节点的、大小为 n 的

二叉搜索树的个数。

则我们可以得到以下式子：

$ G(n) = f(1) + f(2) + + f(n) $

并且当我们分析$ f(i) $的时候，还可以得到这样一个式子：

$ f(i) = G(i-1) * G(n - i) $

因为我们知道，总数为 n 的话，当前节点的两个子树，必然是大小为 i-1 和 n-i 的两棵小

的二叉搜索树。

综合一下两个公式我们就能得到：

$ G(n) = G(0) * G(n - 1) + G(1) * G(n - 2) + + G(n - 1) * G(0) $

而这，就是我们上一题提到的 卡特兰数，有印象吧？

按照上述公式我们就可以写出这么一个题解：

class Solution {

// 方法 numTrees 接收一个整数 n，并返回能够由 n 个不同节点组成的二叉搜索树的数量。

public int numTrees(int n) {

// 如果 n 为 0，按照定义，空树也是一种有效的二叉搜索树。

if (n == 0) {

return 1;

}

// 初始化结果变量 res，用于累加所有可能的二叉搜索树的数量。

int res = 0;

// 遍历每个数字 i，将其作为根节点，以计算所有可能的二叉搜索树。

for(int i = 1; i <= n; i++) {

// 递归计算左子树的数量，左子树包含比根节点小的 i-1 个节点。

int left = numTrees(i - 1);

// 递归计算右子树的数量，右子树包含比根节点大的 n-i 个节点。

int right = numTrees(n - i);

// 将左子树和右子树的组合数量相乘，并加到总数 res 上。

// 这是基于卡特兰数的数学性质，每个左子树都可以与任何一个右子树组合形成唯一的

二叉搜索树。

res += left * right;

}

// 返回计算得出的二叉搜索树的总数量。

return res;

}

}

很遗憾，虽然能正确的计算出答案，但它的效率实在太低了，并不能通过所有的测试点，

n=18 的时候超出了时间限制。

096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91-20231104155102.png

因为它多次重复计算相同的子问题（即存在大量的重复计算），这使得其时间复杂度指数

级增加。

所以我们来改进一下：将已经计算过的 numTrees(i)保存下来。

class Solution {

// 缓存数组，用于存储已经计算过的结果

public int[] nums = new int[20];

// 主方法，计算并返回 n 个节点组成的唯一二叉搜索树的数量

public int numTrees(int n) {

// 基本情况：如果 n 是 0，则有一个空的二叉树

if (n == 0) {

return 1;

}

// 如果之前已经计算过这个结果，直接返回缓存中的值

if (nums[n] != 0) {

return nums[n];

}

// 初始化结果变量 res

int res = 0;

// 遍历每个数字 i，考虑将其作为根节点

for(int i = 1; i <= n; i++) {

// 尝试从缓存中获取左子树的数量

int left = nums[i - 1];

// 如果缓存中没有，则递归计算并更新缓存

if (left == 0) {

nums[i - 1] = numTrees(i - 1);

left = nums[i - 1];

}

// 尝试从缓存中获取右子树的数量

int right = nums[n - i];

// 如果缓存中没有，则递归计算并更新缓存

if (right == 0) {

 nums[n - i] = numTrees(n - i);

right = nums[n - i];

}

// 累加左子树和右子树的组合数量

res += left * right;

}

// 缓存这个结果，以便将来可以重用

nums[n] = res;

// 返回计算得出的二叉搜索树的总数量

return res;

}

}

由于题目描述中，明确给出了提示 1 <= n <= 19，所以我们定义数组 nums 来存储每个

数 n 对应的结果，避免重复计算相同的子问题。

递归会先查看缓存，如果结果不在缓存中，则进行计算并更新缓存，所以效率提高了很

多。

096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91-20231104155255.png

能看得出来，我们采用了“空间换时间”的策略，使得我们的速度变快了不少。我们可以通

过一个具体的例子来说明这个优化的点。

假设我们要计算 numTrees(4)，也就是由 4 个节点能组成的唯一二叉搜索树的数量。不

使用记忆化的递归会进行很多重复计算，因为递归树中会有重叠的子问题。这里是不使用

记忆化时的递归调用树的一个示例：

numTrees(4)

├── numTrees(0) * numTrees(3) // i = 1, 根为 1，左子树为空

│ └── numTrees(3) // 这里开始重复计算 numTrees(3)

│ ├── numTrees(0) * numTrees(2) // i = 1

│ │ └── numTrees(2) // 再次重复计算 numTrees(2)

│ ├── numTrees(1) * numTrees(1) // i = 2

│ └── numTrees(2) * numTrees(0) // i = 3

│ └── numTrees(2) // 再次重复计算 numTrees(2)

├── numTrees(1) * numTrees(2) // i = 2, 根为 2，左子树有 1 个节点

├── numTrees(2) * numTrees(1) // i = 3, 根为 3，右子树有 1 个节点

└── numTrees(3) * numTrees(0) // i = 4, 根为 4，右子树为空

└── numTrees(3) // 再次重复计算 numTrees(3)

在上面的示例中，numTrees(3) 和 numTrees(2) 被计算了多次。

现在，让我们看看加入记忆化后的优化效果：

numTrees(4)

├── numTrees(0) * numTrees(3) // i = 1, 根为 1，左子树为空

│ └── numTrees(3) // 计算 numTrees(3)，结果存入缓存

│ ├── numTrees(0) * numTrees(2) // i = 1

│ │ └── numTrees(2) // 计算 numTrees(2)，结果存入缓存

│ ├── numTrees(1) * numTrees(1) // i = 2

│ └── numTrees(2) * numTrees(0) // i = 3

│ └── numTrees(2) // 直接从缓存读取结果，不再重新计算

├── numTrees(1) * numTrees(2) // i = 2, 根为 2，左子树有 1 个节点

├── numTrees(2) * numTrees(1) // i = 3, 根为 3，右子树有 1 个节点

│ └── numTrees(2) // 直接从缓存读取结果，不再重新计算

└── numTrees(3) * numTrees(0) // i = 4, 根为 4，右子树为空

└── numTrees(3) // 直接从缓存读取结果，不再重新计算

在优化的版本中，我们看到 numTrees(2) 和 numTrees(3) 只计算了一次。它们的结果被

存入 nums 数组。后续的递归调用不再执行计算，而是直接从 nums 数组中读取结果。

这样的优化显著减少了递归调用的次数，因此减少了计算量，提高了效率。

不过，我们还能进一步优化，还记得之前说过的 卡特兰数 吗？

通过前人的经验，可以得到卡特兰数的递推公式：

$ C_0=1, ~~~~C_{n+1}=C_n $

这样子我们就可以既快速又方便地解开这道题：

class Solution {

public int numTrees(int n) {

// 使用 long 类型来存储中间结果，防止溢出

long res = 1;

// 遍历从 0 到 n-1

for (int i = 0; i < n; ++i) {

// 使用卡特兰数的计算公式

// 这里我们使用的是：C(n+1) = 2(2n+1)/(n+2) * C(n)

res = res * 2 * (2 * i + 1) / (i + 2);

}

// 将结果转换为 int 类型返回

// 因为最终结果是确定可以被 int 表示的，所以这里的类型转换是安全的

return (int) res;

}

}

这段代码通过一个 for 循环连续计算$ C_0, C_1, …, C_{n-1} 直 到 C_n

。 在 每 一 步 中 ， 它 利 用 了 这 样 一 个 事 实 ： C_{i+1} 可 以 直 接 通 过 C_i $计

算得到，无需从头开始计算。因此，这种方法只需要线性时间就可以完成计算，非常高

效。

096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91-20231104160439.png

卡特兰数$ C_n $可以用以下递归关系来表示：

$ C_0 = 1 $

$ C_{n+1} = C_n $

现在，如果要计算$ C_3 $，过程应该是这样的：

1.$ C_0 = 1 $（这是基准情况）

2. 对于$ n = 0 到 C_1 $：

$ C_1 = C_0 = = 1 $

3. 对于$ n = 1 到 C_2 $：

$ C_2 = C_1 = = 2 $

4. 对于$ n = 2 到 C_3 $：

$ C_3 = C_2 = = 5 $

对于$ n = 3 $，存在 5 种唯一的二叉搜索树的构造方式。

我们把优化后的递归改成 ACM 输入输出的模式，通过控制台来打印一下结果。

import java.util.Scanner;

public class UniqueBinarySearchTrees {

// 使用一个数组来存储已经计算过的结果

private static int[] cache;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.print("键入 n 的大小: ");

int n = scanner.nextInt();

 // 初始化记忆数组，大小为 n+1，所有值默认为 0

cache = new int[n + 1];

// 计算并打印结果

System.out.println("二叉搜索树的数量 n = " + n + " 是: " + numTrees(n));

}

public static int numTrees(int n) {

if (n <= 1) {

return 1;

}

if (cache[n] != 0) {

return cache[n];

}

int sum = 0;

for (int i = 1; i <= n; i++) {

sum += numTrees(i - 1) * numTrees(n - i);

}

cache[n] = sum;

return sum;

}

}

我们来验证一下，当 n 为 4 的时候，结果是 14，通过卡特兰数的解题方法可以验证一

下，因 n 为 3 的时候结果是 5。

096.%E4%B8%8D%E5%90%8C%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7

%B4%A2%E6%A0%91-20231104162159.png

总结

我们通过总结二叉搜索树的数量，一步一步改进我们的算法，最后使用了卡特兰数的递推

公式得到较好的结果。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees/