LeetCode 96. 不同的二叉搜索树

Categories:

题目描述
思路分析
1. 解法一：动态规划（卡特兰数递推，推荐）
相似题目

题目描述

✅ 96. 不同的二叉搜索树

思路分析

解法一：动态规划（卡特兰数递推，推荐）

核心思路：

BST 性质：若以值 j 为根，则 [1, j-1] 构成左子树（j-1 个节点），[j+1, n] 构成右子树（n-j 个节点）。由于 BST 的结构只取决于节点数（不取决于具体值），子树个数只与节点数有关。

状态定义：dp[i] = i 个节点能构成的不同 BST 数量。

状态转移：枚举根节点 j（1 到 i）：
dp[i] += dp[j-1] * dp[i-j]
左子树 j-1 个节点的方案数 × 右子树 i-j 个节点的方案数。

初始值：dp[0] = 1（空树算 1 种），dp[1] = 1（单节点 1 种）。

数学本质：dp[n] 就是第 n 个卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$，同样出现在括号生成（22 题）、出栈序列等经典问题中。

复杂度分析：

时间复杂度：O(n²)，其中 n 为输入的节点数，双重循环枚举根节点和节点数。

空间复杂度：O(n)，其中 n 为输入的节点数，使用一个长度为 n+1 的 dp 数组。

class Solution {
    public int numTrees(int n) {
        // dp[i] 表示 i 个节点能组成的不同 BST 数量
        int[] dp = new int[n + 1];
        // 初始化边界：空树和单节点各 1 种
        dp[0] = 1;
        dp[1] = 1;
        // 枚举节点总数 i
        for (int i = 2; i <= n; i++) {
            // 枚举根节点 j
            for (int j = 1; j <= i; j++) {
                // 左子树 j-1 个节点，右子树 i-j 个节点
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

func numTrees(n int) int {
    // dp[i] 表示 i 个节点能组成的 BST 数量
    dp := make([]int, n+1)
    // 初始化边界条件
    dp[0], dp[1] = 1, 1

    // 枚举节点总数 i
    for i := 2; i <= n; i++ {
        // 枚举根节点 j
        for j := 1; j <= i; j++ {
            // j 作为根节点，左子树有 j-1 个节点，右子树有 i-j 个节点
            dp[i] += dp[j-1] * dp[i-j]
        }
    }
    return dp[n]
}

相似题目

题目	难度	考察点
95. 不同的二叉搜索树 II	中等	递归、回溯
22. 括号生成	中等	卡特兰数、回溯
894. 所有可能的真二叉树	中等	递归、动态规划
62. 不同路径	中等	组合计数 DP
312. 戳气球	困难	区间 DP
1130. 叶值的最小代价生成树	中等	区间 DP、单调栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/69678908