LeetCode-in-All
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
class Solution {
/**
* @param Integer $n
* @return Integer
*/
public function numTrees($n) {
$result = 1;
for ($i = 0; $i < $n; $i++) {
$result *= 2 * $n - $i;
$result /= $i + 1;
}
$result /= $n + 1;
return (int)$result;
}
}