96. 不同的二叉搜索树

• 题号：96
• 来源：LeetCode
• 难度：中等
• 标签：dp 二叉搜索树 数学
• 语言：TypeScript
• 解法：1 个
• 作者：lmliheng
• 最近更新：2026-09-27

TypeScript · O(n^2) 时间 · O(n) 空间 · 更新于 2026-09-27

卡特兰数 dp，按根划分左右子树相乘

/**
 * @difficulty medium
 * @tags dp,二叉搜索树,数学
 * @time O(n^2)
 * @space O(n)
 * @note 卡特兰数 dp，按根划分左右子树相乘
 * @96. 不同的二叉搜索树
 */

let n: number = 3
let dp: number[] = new Array(n + 1).fill(0) // 共i个节点的所有搜索二叉树数

dp[0] = 1
dp[1] = 1
// 1，2，dp[2]是2，dp[3]是5
for (let i = 2; i < n + 1; i++) { // i指节点数
    //中的值是j， 左边节点数是j-1,右边是i-j
    for (let j = 1; j <= i; j++) {
        dp[i] += dp[j - 1] * dp[i - j]
    }
}

console.log(dp)
console.log(dp[n])

export {};

源码：ts/leetcode/96. 不同的二叉搜索树.ts

---

在 GitHub 上查看题目所在目录：lmliheng/algorithm