LeetCode-in-Rust
96. Unique Binary Search Trees
Medium
Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Example 1:
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
Solution
impl Solution {
pub fn num_trees(n: i32) -> i32 {
let mut result: i64 = 1;
for i in 0..n {
result *= 2 * (n as i64) - (i as i64);
result /= (i + 1) as i64;
}
result /= (n + 1) as i64;
result as i32
}
}