欢迎访问LeetCode题解合集
题目描述
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
题解:
解法一:
动态规划。
设 f[n]
表示 n
个节点组成的二叉搜索树种类数目。
每棵树除了根节点外,左右子树节点个数之和为 n - 1
,左子树的节点个数为 0 ~ n-1
,相应的右子树节点个数为 n-1 ~ 0
,两者组合为乘法关系,所以状态转移为:$f[n] = \sum\nolimits_{i=0}^{n-1} f[i] * f[n - i - 1]$ 。
时间复杂度:$O(n^2)$
额外空间复杂度:$O(n)$
class Solution {
public:
int numTrees(int n) {
vector<int> f(n + 1);
f[0] = 1;
for ( int i = 1; i <= n; ++i ) {
for ( int j = 0; j < i; ++j )
f[i] += f[j] * f[i - j - 1];
}
return f[n];
}
};
/*
时间:0ms,击败:100.00%
内存:6MB,击败:75.83%
*/
法二:
数学公式。
n
个节点构成的不同的二叉树数目为卡特兰数:$\frac{\binom{2n}{n}}{n + 1}$。
直接套公式即可。
class Solution {
public:
using LL = long long;
int numTrees(int n) {
LL ret = 1;
int m = n << 1;
for ( int i = 1; i <= n; ++i )
ret = ret * (m - n + i) / i;
return ret / (n + 1);
}
};
/*
时间:0ms,击败:100.00%
内存:5.8MB,击败:92.83%
*/