LeetCode 96. 不同的二叉搜索树

约 4 分钟
文章信息 11 个分类 6 个标签
分类
LeetCode CodeTop 中等 已解决 20-50 字节跳动 微软 美团 快手 百度 小米
标签
动态规划 数学 树 二叉树 二叉搜索树 卡特兰数问题
目录

题目描述

✅ 96. 不同的二叉搜索树

image-20250419000929377

image-20250507213638874

题意分析

给定整数 n，节点值恰好是 1 到 n 这 n 个互不相同的数，问能构造出多少棵结构上互不相同的二叉搜索树。

这里有两个约束叠在一起。一是二叉搜索树的性质：任意节点的左子树所有值都小于它，右子树所有值都大于它。二是节点值集合是固定的连续整数，不能重复也不能缺失。两条合起来意味着——一旦选定了根节点的值，整棵树的「哪些值去左边、哪些值去右边」就被完全确定了，没有任何自由度，剩下的自由度只在左右子树各自的形状上。

「结构不同」指的是树的形态不同。由于值的分配被 BST 性质锁死，形态不同和整棵树不同其实是一回事，不会出现两棵形状相同但填值不同的树。

约束是 1 <= n <= 19。这个上限值得留意：n = 19 时答案是 1767263190，刚好塞进 32 位有符号整数，说明出题人特意把范围卡在不溢出的位置，也暗示答案增长得非常快，是指数级的。

边界方面，n = 1 时只有一棵树；而在递推过程中一定会遇到「子树为空」的情形，空树必须被算作一种合法形态，否则乘法会把整条路径清零。

解法：Catalan 动态规划

核心思路

问题关键：题目只问数量，不应真的构造所有树。BST 的结构只取决于键的相对大小，因此任意 k 个有序键能形成的结构数都相同，可以只按节点数做状态。

状态与推导：令 dp[k] 表示 k 个有序键能组成的 BST 数量。若第 root 个键作为根，左边有 root-1 个键，右边有 k-root 个键；左右结构可独立组合，因此该根贡献

dp[root - 1] * dp[k - root]

枚举所有互斥的根位置并求和：

dp[k] = Σ dp[root - 1] * dp[k - root]，其中 1 <= root <= k。

边界与不变量：dp[0] = 1，表示空子树只有一种选择，也是乘法单位元。计算 dp[k] 时，所有更小规模的状态都已经确定。

正确性：任意 BST 都有唯一根位置，并唯一拆成一棵左子树和一棵右子树；反过来，任选一个根位置及其左右结构，也能唯一组成合法 BST。因此每类方案既不遗漏也不重复，乘积再求和恰好得到全部结构数。

解题步骤

  1. 建立 dp[0..n]，令 dp[0] = 1。
  2. 按 nodes = 1..n 递增计算，保证转移需要的小规模答案已就绪。
  3. 枚举根的位置 root = 1..nodes，累加 dp[root-1] * dp[nodes-root]。
  4. 返回 dp[n]。

口述样例：n = 3 时，根分别在第 1、2、3 位，贡献为 dp[0]dp[2] + dp[1]dp[1] + dp[2]dp[0] = 2+1+2 = 5。

边界检查：根为最小值或最大值时，一侧为空；正因为 dp[0] = 1，这些合法结构才不会被乘成 0。

代码实现

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int nodes = 1; nodes <= n; nodes++) {
            for (int root = 1; root <= nodes; root++) {
                dp[nodes] += dp[root - 1] * dp[nodes - root];
            }
        }
        return dp[n];
    }
}

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1

    for nodes := 1; nodes <= n; nodes++ {
        for root := 1; root <= nodes; root++ {
            dp[nodes] += dp[root-1] * dp[nodes-root]
        }
    }
    return dp[n]
}

复杂度分析

  • 时间复杂度：$O(n^2)$，总转移次数为 $1+2+\cdots+n$。
  • 空间复杂度：$O(n)$，保存 n+1 个规模的答案。

关键点总结

  • 只求数量时做计数 DP，不要构造指数级的树集合。
  • 不同根的方案互斥，所以求和；左右子树独立，所以相乘。
  • dp[0] = 1 表示一种「空的选择」，不是存在一个空节点。
  • 这就是卡特兰递推。闭式可做到 $O(n)$，但组合数中间值有溢出风险，面试手写 DP 更稳。

易错点总结

  • 将 dp[0] 留为默认值 0：所有包含空子树的乘积都会归零。
  • 把左右方案相加，或把不同根的贡献相乘：混淆了独立组合与互斥分类。
  • 写成赋值而不是累加：只会保留最后一个根位置的贡献。
  • 将左子树规模写成 root：根本身不属于子树，正确值是 root-1。
  • 擅自取模：本题要求精确答案，且约束保证结果在 32 位有符号整数内。

相似题目

题目 难度 考察点
95. 不同的二叉搜索树 II 中等 要输出全部树而不止计数，必须递归建树并做左右子树的笛卡尔积
22. 括号生成 中等 合法括号序列个数同为卡特兰数，但本题要枚举方案，用回溯加剪枝
241. 为运算表达式设计优先级 中等 同样按「枚举分割点、左右独立组合」拆分，但组合的是计算结果集合