分析
根结点固定时平衡二叉树个数=左孩子的个数 * 右孩子的个数。又左孩子或右孩子为空是不妨置为1，这样
0个结点时，f(0) = 1
1个结点时，f(1) = f(0) * f(0) = 1
2个结点时，f(2) = f(0) * f(1) + f(1) * f(0)
3个结点时，f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0)
规律
n个结点时： f(n) = f(0) * f(n-1) + f(1) * f(n-2) + ... *f(n-1) * f(1)
为了记忆原来的值，用容器（数组）存一下。
参考代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class
Solution {
public
:
int
numTrees(
int
n) {
if
(n <= 0)
return
0;
vector<
int
> vec;
vec.push_back(1);
vec.push_back(1);
for
(
int
i = 2; i <= n; ++i)
{
int
tmp = 0;
for
(
int
j = 0; j < i; ++j)
tmp += vec[j] * vec[i - 1 - j];
vec.push_back(tmp);
}
return
vec[n];
}
};
|
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3652976.html，如需转载请自行联系原作者
