题目描述：
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
数据范围：
$1\le n \le 8$
题解：
前一题，96. 不同的二叉搜索树 方案数就是左侧乘以右侧。所以左侧会有多种选择，右侧也有多种选择，需要进行组合。此外需要枚举树根，得到左侧右侧列表，然后组合，组合的时候创建根节点，接上左右子树。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<TreeNode *> dp(int l, int r)
{
if (l > r)
return {nullptr};
vector<TreeNode *> ret;
for (int i = l; i <= r; ++i)
{
auto left = dp(l, i - 1);
auto right = dp(i + 1, r);
for (auto &l : left)
{
for (auto &r : right)
{
TreeNode *root = new TreeNode(i);
root->left = l, root->right = r;
ret.push_back(root);
}
}
}
return ret;
}
vector<TreeNode *> generateTrees(int n)
{
return dp(1, n);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int mm[20] = {1, 1, 2, 5};
int dp(int n)
{
if(mm[n] != 0)
return mm[n];
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += dp(i - 1) * dp(n - i);
}
return mm[n] = ans;
}
int numTrees(int n)
{
return dp(n);
}
};
|