p.p1
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]

Code

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 0) return new ArrayList<>();
        if (n == 1) {
            List<Integer> list = new ArrayList<>();
            list.add(0);
            return list;
        }
        
        List<Integer>[] degrees = new ArrayList[n];
        
        for (int i = 0; i < degrees.length; i++) {
            degrees[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < edges.length; i++) {
            int a = edges[i][0], b = edges[i][1];
            degrees[a].add(b);
            degrees[b].add(a);
        }
        
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i].size() == 1) leaves.add(i);
        }
        
        int remain = n;
        while (remain > 2) {
            int size = leaves.size();
            remain -= size;
            
            List<Integer> newLeaves = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                int leaf = leaves.get(i);
                for (int j = 0; j < degrees[leaf].size(); j++) {
                    int remove = degrees[leaf].get(j);
                    degrees[remove].remove(Integer.valueOf(leaf));
                    if (degrees[remove].size() == 1) newLeaves.add(remove);
                }
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

Solution

找到所有入度為1的節(jié)點(diǎn)硝枉，這些節(jié)點(diǎn)都是葉子節(jié)點(diǎn)。通過BFS移除這些節(jié)點(diǎn)。剩余所有節(jié)點(diǎn)中入度為1的是新的葉子節(jié)點(diǎn)。循環(huán)直至剩余2個(gè)以下的節(jié)點(diǎn)為止。