题目描述
给定一个 n,求共有多少种不同的 BST(二叉搜索树),满足中序遍历是 1…n。
样例
输入:3
输出:5
解释:
给定 n = 3, 共有5种不同的二叉搜索树,如下所示:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
算法
(动态规划) O(n2)
状态表示:f[n] 表示 n个节点的二叉搜索树共有多少种。
状态转移:左子树可以有 0,1,…n−1 个节点,对应的右子树有 n−1,n−2,…,0 个节点,f[n] 是所有这些情况的加和,所以 f[n]=∑n−1k=0f[k]∗f[n−1−k]。
时间复杂度分析:状态总共有 n 个,状态转移的复杂度是 O(n),所以总时间复杂度是 O(n2)。
C++ 代码
class Solution {
public:
int numTrees(int n) {
vector<int>f(n + 1);
f[0] = 1;
for (int i = 1; i <= n; i ++ )
{
f[i] = 0;
for (int j = 1; j <= i; j ++ )
f[i] += f[j - 1] * f[i - j];
}
return f[n];
}
};
这个是不是卡特兰数?
是的。
f[i] = 0
貌似没有必要,因为i层之前不会更新第i层,所以本身就是0.对滴,可以去掉。
y总这样是怎样保证是二叉搜索树的?
可以保证对于每个子树:根节点左边的所有点都小于根节点,右边的所有点都大于根节点。
请教下y总,这是怎么保证的呢,是确定了左右子树的节点个数之后,自动按照搜索树的规则成树吗?