96\. Unique Binary Search Trees
# 96. Unique Binary Search Trees (opens new window)
# Description
Difficulty: Medium
Related Topics: Math (opens new window), Dynamic Programming (opens new window), Tree (opens new window), Binary Search Tree (opens new window), Binary Tree (opens new window)
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
1
2
2
Example 2:
Input: n = 1
Output: 1
1
2
2
Constraints:
1 <= n <= 19
# Solution
Language: JavaScript
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
let res = 1;
for (let i = 0; i < n; ++i)
res = res * 2 * (2 * i + 1) / (i + 2);
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12