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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
// 95. Unique Binary Search Trees II
#include <stdlib.h>
/*
* given an integer 'n', return all the structurally unique BST's which has
* exactly 'n' nodes of unique values from 1 to 'n'. return the answer in any
* order.
*/
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode **process(int begin, int end, int *return_size, int *tree_num) {
if (begin > end) {
struct TreeNode **res = malloc(sizeof(struct TreeNode *));
*return_size = 1;
res[0] = NULL;
return res;
}
if (begin == end) {
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = begin;
root->left = NULL;
root->right = NULL;
struct TreeNode **res = malloc(sizeof(struct TreeNode *));
res[0] = root;
*return_size = 1;
return res;
}
int idx = 0;
struct TreeNode **res =
malloc(tree_num[end - begin + 1] * sizeof(struct TreeNode *));
for (int i = begin; i <= end; i++) {
int ln, rn;
struct TreeNode **l = process(begin, i - 1, &ln, tree_num);
struct TreeNode **r = process(i + 1, end, &rn, tree_num);
for (int m = 0; m < ln; m++) {
for (int n = 0; n < rn; n++) {
struct TreeNode *root = malloc(sizeof(struct TreeNode));
root->val = i;
root->left = l[m];
root->right = r[n];
res[idx] = root;
idx++;
}
}
}
*return_size = idx;
return res;
}
struct Treenode **generateTrees(int n, int *return_size) {
int *tree_num = calloc(n + 1, sizeof(int));
tree_num[0] = 1;
tree_num[1] = 1;
for (int i = 2; i <= n; i++)
for (int j = 0; j < i; j++)
tree_num[i] += tree_num[j] * tree_num[i - 1 - j];
return process(1, n, return_size, tree_num);
}
|