aboutsummaryrefslogtreecommitdiff
path: root/min_height_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_height_tree.c')
-rw-r--r--min_height_tree.c64
1 files changed, 64 insertions, 0 deletions
diff --git a/min_height_tree.c b/min_height_tree.c
new file mode 100644
index 0000000..a5cac34
--- /dev/null
+++ b/min_height_tree.c
@@ -0,0 +1,64 @@
+// 310. Minimum Height Trees
+#include "leetcode.h"
+
+/*
+ * a tree is an undirected graph in which any two vertices are connected by
+ * exactly one path. in other words, any connected graph without simple cycles
+ * is a tee. given a tree of 'n' nodes from 0 to 'n - 1' and an array of 'n - 1'
+ * edges where 'edges[i] = [ai, bi]' indicates that there is an undirected edge
+ * between the two nodes 'ai' and 'bi'in the the tree, you can choose any node
+ * of the tree as the root. return a list of all mht's root labels. you can
+ * return the answer in any order.
+ */
+
+int *findMinHeightTrees(int n, int **edges, int edgesSize, int *edgesColSize,
+ int *returnSize) {
+ int *ans = (int *)malloc(sizeof(int) * n);
+ *returnSize = 0;
+ if (n == 1) {
+ (*returnSize)++;
+ ans[*returnSize - 1] = 0;
+ return ans;
+ }
+ int **graph = (int **)malloc(sizeof(int *) * n);
+ for (int i = 0; i < n; i++)
+ graph[i] = (int *)malloc(sizeof(int));
+ int *col_sizes = (int *)calloc(n, sizeof(int));
+ for (int i = 0; i < *returnSize; i++) {
+ int begin = edges[i][0], end = edges[i][1];
+ col_sizes[begin]++;
+ graph[begin] = (int *)realloc(graph[begin], sizeof(int) * col_sizes[begin]);
+ graph[begin][col_sizes[begin] - 1] = end;
+ col_sizes[end]++;
+ graph[end] = (int *)realloc(graph[end], sizeof(int) * col_sizes[end]);
+ graph[end][col_sizes[end] - 1] = begin;
+ }
+ int *degrees = (int *)malloc(sizeof(int) * n);
+ for (int i = 0; i < n; i++) {
+ degrees[i] = col_sizes[i];
+ if (col_sizes[i] == 1) {
+ (*returnSize)++;
+ ans[*returnSize - 1] = i;
+ }
+ }
+ int cnt = n, next = 0;
+ int *next_level = (int *)malloc(sizeof(int) * n);
+ while (cnt > 2) {
+ for (int i = 0; i < *returnSize; i++) {
+ int end = ans[i];
+ cnt--;
+ for (int k = 0; k < col_sizes[end]; k++) {
+ int begin = graph[end][k];
+ degrees[begin]--;
+ if (degrees[begin] == 1)
+ next_level[next++] = graph[end][k];
+ }
+ }
+ *returnSize = next;
+ next = 0;
+ int *tmp = ans;
+ ans = next_level;
+ next_level = tmp;
+ }
+ return ans;
+}