96.不同的二叉搜索树
- 题目:
1 | 给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? |
思路:首先明确二叉搜索树BST的规则:左子节点的key小于root的key小于右子节点的key。那么当我们有
1~n
n个元素的时候,任意一个元素作为根节点,左子节点(树)只能选择比它小的,e.g.有m
种,右子节点(树)只能选择比它大的,e.g.有n
种,那么这个node有mn
种选择。想到这里很容易想到用递归解决:然而这中间需要求值,我们可以保存已经求解过的值避免重复计算,动态规划;
- 函数的功能是求二叉搜索树的组合方式有多少种
- 结束条件是元素序列中元素个数为1(输入不为0),只有1种组合方式
- (动态规划的)递推公式:一棵树的组合方式个数为对每种
root
的值对应的左右子树组合方式个数之积求和。
递归代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int numTrees(int n) {
if(n<2) return 1;
int sum = 0;//局部变量不初始化会出错
for(int i=1; i<=n; ++i){
int numL = i-1;
int numR = n-i;
sum += numTrees(numL)*numTrees(numR);
}
return sum;
}
};可以通过单个n比较小的测试用例,但是大的n会超时,分析递归的时间复杂度:
T(N)=2NT((N-1)/2)
,O(N)=N^logN
,没错的话应该是这样,非常大。题目答案为动态规划:与其自上而下去递归计算,不如自下而上先求解n比较小的时候的情况,保存在容器中,求解更大n的时候直接利用计算结果,小的空间换很多时间。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int numTrees(int n) {
if(n<2) return 1;
vector<int> num(n+1);
num[0] = num[1] = 1;
for(int i=2; i<=n; ++i){
int sum = 0;
for(int j=1; j<=i; ++j){
sum += num[j-1]*num[i-j];
}
num[i] = sum;
}
return num[n];
}
};总结:此动态规划区别于递归写法之处:不调用自身。递归是从任意输入,通过调用自己,每一次收敛输入值,最终求得输入很小时的解,然后层层返回。而动态规划为了规避重复运算,从较小的解开始求解,由于求任意输入的解时都需要用到更小输入的解,每次运算保存小输入解的值,直至对输入进行求解。动态规划保证了没有重复计算的解。时间复杂度:
$$
O(N(N+1)/2)=O(N^2)
$$
空间复杂度:O(N)
。数学演绎法(套公式):卡塔兰数:只记结论:
卡塔兰数
C_n
,
$$
C_0=C_1=1,C_{n+1}=\frac{2(2n+1)} {n+2}C_n
$$
这个公式即为动态规划种内循环的解。