Unique Binary Search Trees

Description

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
1         3     3      2      1
\       /     /      / \      

3     2     1      1   3      2
/     /       \                 

2     1         2                 3

 

Constraints:

• 1 <= n <= 19

Solution(javascript)

// const numTrees = (n) => {
//   const numbers = new Array(n).fill(0).map((v, index) => index + 1)
//   const memo = {}
//   const aux = (list = []) => {
//     const key = list.toString()
//     if (memo[key] !== undefined) {
//       return memo[list.toString()]
//     }
//     if (list.length <= 1) {
//       return 1
//     }
//     memo[key] = list.reduce((acc, number) => acc + (
//       aux(list.filter(x => x < number)) * aux(list.filter(x => x > number))
//     ), 0)
//     return memo[key]
//   }
//   return aux(numbers)
// }

// const numTrees = (n) => {
//   const memo = {}
//   const aux = (current) => {
//     if (memo[current] !== undefined) {
//       return memo[current]
//     }
//     if (current <= 1) {
//       return 1
//     }
//     let res = 0
//     for (let i = 0; i <= current - 1; i++) {
//       res += aux(i) * aux(current - i - 1) // 左右子树的情况
//     }
//     memo[current] = res
//     return memo[current]
//   }
//   return aux(n)
// }

// O(n) catalan numbers
const binomialCoefficient = (n, k) => {
  if (n - k < k) {
    k = n - k
  }
  let res = 1
  for (let i = 1; i <= k; i++) {
    res *= n - i + 1
    res /= i
  }
  return res
}
const numTrees = n => binomialCoefficient(2 * n, n) / (1 + n)