【Leetcode】【Medium】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         3     3      2      1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

解题:

单纯的看做一个数列题:1, 2, 5, 14, 42, 132, ... , 求通项。

这是一个典型的卡塔兰数,中国人明安图比卡塔兰早100多年就发现了这种数列,其实更应该叫明安图数。

程序实现不用这么做,不过还是给出通项公式:f(n) = (2n)! / [(n+1)! * n!];

在原列前补充一个值为1的0位:1, 1, 2, 5, 14, 42, 132, ...

则从新数列第3个数(2)开始,f(n) = f(0) * f(n-1)  +  f(1) * f(n-2)  +  ...  +  f(n-1) * f(0);

代码:

 class Solution {
public:
int numTrees(int n) {
if (n == )
return ;
vector<int> res(n+, );
res[] = res[] = ; for (int i = ; i <= n; ++i) {
for (int j = ; j < i; ++j) {
res[i] += res[j] * res[i--j];
}
} return res[n];
}
};

Leetcode测试集中没有考察n为0的情况,我认为n为0时还是有意义的,应该返回0。

上一篇:【leetcode】Unique Binary Search Trees


下一篇:【LeetCode】Unique Binary Search Trees II 异构二叉查找树II