LeetCode 96. 不同的二叉搜索树 Rust 实现函数签名 pub fn num_trees(n: i32) - i32解法1动态规划 O(n²)rustpub 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}{n1}\dbinom{2n}{n}rustpub 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}}要点使用 i64 防止中间乘法溢出。公式版时间 O(n)、空间 O(1)。n ≤ 19i32 可以存下结果。需要 C / Go / Java / TypeScript 版本吗 豆包 LeetCode 96. 不同的二叉搜索树 Rust实现
LeetCode 96. 不同的二叉搜索树 Rust 实现函数签名 pub fn num_trees(n: i32) - i32解法1动态规划 O(n²)rustpub 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}{n1}\dbinom{2n}{n}rustpub 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}}要点使用 i64 防止中间乘法溢出。公式版时间 O(n)、空间 O(1)。n ≤ 19i32 可以存下结果。需要 C / Go / Java / TypeScript 版本吗 RELATED READING
延伸阅读
更多一线实战笔记与深度复盘，助您持续精进
