分析
根结点固定时平衡二叉树个数=左孩子的个数 * 右孩子的个数。又左孩子或右孩子为空是不妨置为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]; }}; |
Unique Binary Search Trees,布布扣,bubuko.com
原文：http://www.cnblogs.com/kaituorensheng/p/3652976.html