Question
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
Related Topics 树 二叉搜索树 数学 动态规划 二叉树 👍 2126 👎 0
Answer
//95,返回所有的子树
//96
//n = 3
//5
//1.1~n中n个数字为root，求以i为根的bst个数
//2.以i为根的左子树个数 * 以i为根的右子树的个数 = 以i为根的bst个数
//3.以i为根的左子树，有1～i-1这些数字组成(i-1个)；以i为根的右子树，以i+1～n这些数字组成(n-i个)
int dfs0(int n) {
int ans = 0;
if (n==0 ||n==1)
return 1;//n==0时返回1，否则相乘为0
for (int i = 1; i <= n; ++i) {
ans += dfs0(i-1)*dfs0(n-i);
}
return ans;
}
int numTrees0(int n) {
//暴力法，Time Limit Exceeded，o(n!)
return dfs0(n);
}
int dfs1(vector<int> &store, int n) {
int ans = 0;
if (n==0 || n==1) {
return 1;
}
if (store[n] != -1) {
return store[n];
}
for (int i = 1; i <= n; ++i) {
store[i-1] = dfs1(store, i-1);
store[n-i] = dfs1(store, n-i);
ans += store[i-1]*store[n-i];
}
return ans;
}
int numTrees1(int n) {
//vec存下计算过的数量，避免超时
vector<int> store(n+1, -1);
return dfs1(store, n);
}
// f[i] : 表示以i为根节点组成的树的个数，对于每个f[i] = G[i-1] * G[n-i]
// G[n] : 表示n个节点组成的二叉树的个数
// G[n] = f[1] + f[2] + ... + f[n];
// G[n] = G[0]*G[n-1] + G[1]*G[n-2] + ....G[n-1]*G[0]
// G[2] = f[1] + f[2] = G[0]*G[1] + G[1]*G[0]
// G[3] = G[0]*G[2] + G[1]*G[1] + G[2]*G[0]
int numTrees2(int n) {
//o(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];
}
Attention
- 结论一：以i为根的左子树，有1～i-1这些数字组成(i-1个)；以i为根的右子树，以i+1～n这些数字组成(n-i个)
- 结论二：以i为根的左子树个数 * 以i为根的右子树的个数 = 以i为根的bst个数
- numTrees0方法超时，可以通过
vector<int> store(n+1, -1)记录下已经计算过的组合数量 - 注意递归边界：
n==0 || n==1 - numTrees2是动态规划
