题目描述
给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。
题解
居然连二叉搜索树是啥都不记得了 嘤
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
So, 递归吧。
理解了思路，代码还是很好写的。不过，有点懵比的是，让我觉得效率很低的递归，居然：
执行用时 :12 ms, 在所有 C++ 提交中击败了93.46%的用户
内存消耗 :15.9 MB, 在所有 C++ 提交中击败了87.26%的用户
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
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<TreeNode*> makeTree(int left, int right)
{
vector<TreeNode*> res;
TreeNode *r;
if (left >= right)
{
if (left > right)return { NULL };
r= new TreeNode(left);
return { r };
}
for (int i = left; i <= right; i++)
{
vector<TreeNode*> lefts = makeTree(left, i - 1);
vector<TreeNode*> rights = makeTree(i + 1, right);
for (int j = 0; j < lefts.size(); j++)
{
for (int k = 0; k < rights.size(); k++)
{
r = new TreeNode(i);
r->left = lefts[j];
r->right = rights[k];
res.push_back(r);
}
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
if (n < 1)return{};
return makeTree(1, n);
}
|
那，如果改成引用传参呢？
不改了，没意思。下一个。
题目描述
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
题解
像上面一样递归也可以，但是动态规划是不是更合适。嗯主要原因是n=19时，运行超出时间限制了……
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int numTrees(int n) {
if (n < 2)return n;
int *countTree = new int[n+1];
countTree[0] = 1;
countTree[1] = 1;
for (int i = 2; i <= n; i++)
countTree[i] = 0;
for (int i = 2; i <= n; i++)
{
for (int j = 0; j < i; j++)
{
countTree[i] += countTree[j] * countTree[i - j - 1];
}
}
return countTree[n];
}
|
执行用时 :4 ms, 在所有 C++ 提交中击败了61.10%的用户
内存消耗 :7.4 MB, 在所有 C++ 提交中击败了100.00%的用户