aboutsummaryrefslogtreecommitdiff
path: root/unique_bst2.c
diff options
context:
space:
mode:
Diffstat (limited to 'unique_bst2.c')
-rw-r--r--unique_bst2.c63
1 files changed, 63 insertions, 0 deletions
diff --git a/unique_bst2.c b/unique_bst2.c
new file mode 100644
index 0000000..8b48961
--- /dev/null
+++ b/unique_bst2.c
@@ -0,0 +1,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);
+}