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
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

思路

投机取巧了一下。这道题可以将问题转化成，知道一棵树的中序遍历，我们能够构造出几棵不同的树？最后的结果是一组Catalan Number（明安图-卡塔兰数）。这个规律其实一开始是由我们中国的一位老祖先发现的。卡塔兰数的一般项公式为 (1/n+1) * C(n,2n)，从而得到解。

当然也可以用动态规划/递归的方式解决。

譬如[1,2,3,4], 取 1 为根节点，右边的子树2，3，4是有序的，取1为根节点的结果是1 numTrees(3) = 5, 取2为根节点的结果是 1 numTrees(2) = 2, 取3为根节点的结果是2, 取4为根节点的结果是5，所以我们可以得到numTrees(4) = 14。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int numTrees(int n) {
        //Return a catalan number
        double res = 1;
        for(int i = 0; i < n; i++){
            double tmp = (2.0 * n - i) / (n - i);
            res *= tmp;
        }
        double a = res / (n + 1.0);
        return round(a);
    }
};