diff options
Diffstat (limited to 'min_height_tree.c')
-rw-r--r-- | min_height_tree.c | 64 |
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; +} |