- 困难
- 中等
- 简单
题目描述
给定一个整数 n,求以 1 … n 为节点组成的二叉搜索树有多少种?来源,leetcode 每日一题 96. 不同的二叉搜索树
示例:
输入:3
输出:5
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
- 递归的想法,二叉树是有序树,对于一棵树而言,当第i个节点为根时,其将[1,i-1]和[i+1, n]分成了两个子树,则此时只需要对两个子树分别构建,然后将他们拼接到i上即可。
- 需要学会问题分解!
代码
class Solution {
public:
int numTrees(int n) {
vector<int> G(n + 1, 0);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
};
class Solution {
public:
int numTrees(int n) {
long long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int)C;
}
};