leetcode做题记录 —— unique-binary-search-trees

unique-binary-search-trees 
Given n, how many structurally unique BST’s (binary search trees) that 
store values 1…n?

For example, Given n = 3, there are a total of 5 unique BST’s.

1.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3

unique-binary-search-trees

求n个节点的搜索二叉树的的总数 
比如，n = 3 的时候，总共有5总不同的解构

1.   1         3     3      2      1
2.    \       /     /      / \      \
3.     3     2     1      1   3      2
4.    /     /       \                 \
5.   2     1         2                 3

参考来源

一颗节点为 n 搜索二叉树的数量等于，根节点左子树的总数 + 根节点右子树的总数，根节点从 1 到 n 。

解法一，递归

递归的解法很好理解，就是性能太差，leetcode会超时

1.//Javascript
2./**
3. * @param {number} n
4. * @return {number}
5. */
6.var numTrees = function(n) {
7.    if( n === 0 )
8.        return 1;
9.    let k = 0;
10.    let end = n - 1;
11.    let nums = 0;
12.    while( k <= end)
13.    {
14.        nums += numTrees(k) * numTrees(end - k);
15.        k++;
16.    }
17.    return nums;
18.};

解法二，迭代

1.//Javascript
2./**
3. * @param {number} n
4. * @return {number}
5. */
6.var numTrees = function(n) {
7.    let res = [1, 1, ...new Array(n-1).fill(0)];
8.    for( let i = 2; i <= n; i++ )
9.    {
10.        for( let j = 0; j < i; j++ )
11.        {
12.            res[i] += res[j] * res[i - j - 1];
13.        }
14.    }
15.    return res[n];
16.};

解法三，卡塔兰数

卡塔兰数

由于这道题的模型正好是卡塔兰数的定义，所以可以直接用卡塔兰数的计算公式

1.//Javascript
2./**
3. * @param {number} n
4. * @return {number}
5. */
6.var numTrees = function(n) {
7.    return binomialCoeff(2 * n, n) - binomialCoeff(2 * n, n + 1);
8.};
9.var binomialCoeff = function(n, m) {
10.    return factorial(n) / (factorial(m) * factorial(n - m));
11.}
12.var factorial = function(n) {
13.    let res = 1;
14.    while(n > 0)
15.    {
16.        res *= n--;
17.    }
18.    return res;
19.};

End