leetcodesolutions/code/310.minimum-height-trees.java at main · Raghuram42/leetcodesolutions · GitHub

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
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        ArrayList<Integer> res = new ArrayList<Integer>();
        if (edges.length == 0) {
            res.add(0);
            return res;
        }
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();

        for(int i=0;i<n;i++)
            graph.put(i, new ArrayList<Integer>());

        int[] degr = new int[n];
        for(int i=0;i<edges.length;i++){
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
            degr[edges[i][0]]++;
            degr[edges[i][1]]++;
        }


        Queue<Integer> que = new LinkedList<Integer>();

        for(int i=0;i<n;i++)
            if(degr[i] == 1)
                que.offer(i);

        int c =0;
        while(!que.isEmpty()){

            int sz = que.size();
            c+=sz;

            for(int i=0;i<sz;i++){
                Integer id = que.poll();
                degr[id]--;

                  if (c == n) res.add(id);
                for (Integer adjId : graph.get(id)) {

                    if (degr[adjId] != 0) {
                        degr[adjId]--;
                        if (degr[adjId] == 1) que.offer(adjId);
                    }
                }
            }
            }
        return res;
        }

    }