aboutsummaryrefslogtreecommitdiff
path: root/min_height_tree.c
blob: a5cac343d1fbc35f4d5f9c3c611034931462ed62 (plain)
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
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;
}