豆包 LeetCode 96. 不同的二叉搜索树 Rust实现

LeetCode 96. 不同的二叉搜索树 Rust 实现

函数签名： pub fn num_trees(n: i32) -> i32

解法1：动态规划 O(n²)

rust

pub struct Solution;

impl Solution {
pub fn num_trees(n: i32) -> i32 {
let n = n as usize;
let mut dp = vec![0; n + 1];
dp[0] = 1;
dp[1] = 1;

for i in 2..=n { for j in 1..=i { dp[i] += dp[j - 1] * dp[i - j]; } } dp[n] }

}

dp[i]：i 个节点能够组成的二叉搜索树数量。
枚举根 j，左子树 j‑1 个点，右子树 i‑j 个点，乘积累加。

解法2：卡特兰数学公式 O(n)（最优）

卡特兰数：C_{n}=\dfrac{1}{n+1}\dbinom{2n}{n}

rust

pub struct Solution;

impl Solution {
pub fn num_trees(n: i32) -> i32 {
let mut res: i64 = 1;
for i in 1…=n as i64 {
res = res * (n as i64 + i) / i;
}
res = res / (n as i64 + 1);
res as i32
}
}

要点

1. 使用 i64 防止中间乘法溢出。
2. 公式版时间 O(n)、空间 O(1)。
3. n ≤ 19，i32 可以存下结果。

需要 C++ / Go / Java / TypeScript 版本吗？