Minimum Height Trees LeetCode solution in C++

1
class Solution {
2
 public:
3
  int getheight(vector<int> a[], int sv, int n) {
4
    int lvl = 0;
5
    vector<int> vis(n, 0);
6
    queue<int> q;
7
    q.push(sv);
8
    vis[sv] = 0;
9
    while (q.size()) {
10
      int sz = q.size();
11
      lvl++;
12
      while (sz--) {
13
        int curr = q.front();
14
        q.pop();
15
        vis[curr] = 1;
16

17
        for (auto it : a[curr]) {
18
          if (vis[it] == 0) {
19
            q.push(it);
20
          }
21
        }
22
      }
23
    }
24
    return lvl;
25
  }
26
  vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
27
    vector<int> a[n];
28
    vector<int> indegree(n, 0);
29
    for (auto it : edges) {
30
      a[it[0]].push_back(it[1]);
31
      a[it[1]].push_back(it[0]);
32
      indegree[it[0]]++;
33
      indegree[it[1]]++;
34
    }
35

36
    // cutting leafs whose indegree is 1
37
    queue<int> q;
38
    vector<int> ans;
39
    for (int i = 0; i < n; i++) {
40
      if (indegree[i] == 1) {
41
        q.push(i);
42
        indegree[i]--;
43
      }
44
    }
45

46
    while (q.size()) {
47
      int sz = q.size();
48
      ans.clear();
49
      while (sz--) {
50
        int curr = q.front();
51
        q.pop();
52
        ans.push_back(curr);
53
        for (auto it : a[curr]) {
54
          indegree[it]--;
55
          if (indegree[it] == 1) q.push(it);
56
        }
57
      }
58
    }
59

60
    if (n == 1) return {0};
61

62
    return ans;
63

64
    // brute force gives tle
65
    //         int mn = INT_MAX;
66
    //         unordered_map<int,vector<int>> mp;
67
    //         for(int i = 0;i<n;i++)
68
    //         {
69
    //             int x = getheight(a,i,n);
70
    //             mp[x].push_back(i);
71

72
    //             // cout<<i<<" "<<x<<endl;
73

74
    //             mn = min(mn,x);
75
    //         }
76

77
    //         return mp[mn];
78
  }
79
};