310. Minimum Height Trees

LeetCode Link

思路：按层剪掉 leaf nodes，当最终只剩一个或者两个 nodes，即为题解

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    LinkedList<Integer> res = new LinkedList<>();
    if (n == 1) {
        res.add(0);
        return res;
    }


    int[] indegrees = new int[n];
    HashMap<Integer, List<Integer>> map = new HashMap<>();

    for (int[] edge: edges) {
        indegrees[edge[0]]++;
        indegrees[edge[1]]++;
        if (!map.containsKey(edge[0])) {
            map.put(edge[0], new LinkedList<Integer>());
        }
        map.get(edge[0]).add(edge[1]);
        if (!map.containsKey(edge[1])) {
            map.put(edge[1], new LinkedList<Integer>());
        }
        map.get(edge[1]).add(edge[0]);
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (indegrees[i] == 1) {
            queue.offer(i);
        }
    }

    int visitedSize = 0;
    while (!queue.isEmpty()) {
        if (visitedSize >= n - 2) {
            break;
        }

        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int node = queue.poll();
            indegrees[node]--;
            visitedSize++;
            for (Integer neighbor: map.get(node)) {
                if (indegrees[neighbor] == 0) {
                    continue;
                }
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 1) {
                    queue.offer(neighbor);
                }
            }
        }
    }

    while (!queue.isEmpty()) {
        res.add(queue.poll());
    }
    return res;
}

可以使用 HashMap<Integer, Set<Integer>> map，这样就不用使用 indegrees array 了。思路是一致的，Graph Topological sort based on BFS.