Minimum Height Trees
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, is the same as and thus will not appear together in edges.
Example 1:
Given n = 4, edges = , , ]
0
|
1
/ \
2 3
return
Example 2:
Given n = 6, edges = , , , , ]
0 1 2
\ | /
3
|
4
|
5
return
一道图的题目,我们可以每次都删除叶子节点,维护一个入度为1的队列,删除叶子节点的同时,将新的入度为0的及诶单更新到队列中,直到最后剩下一个或两个节点。代码如下:
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer>[] graph = new List[n];
Queue<Integer> queue = new LinkedList<Integer>();
List<Integer> list = new ArrayList<Integer>();
int[] degree = new int[n];
if(n == 1) {
list.add(0);
return list;
}
if(edges == null || edges.length == 0) return list;
for(int i = 0; i < edges.length; i++) {
if(graph[edges[i][0]] == null)
graph[edges[i][0]] = new ArrayList<Integer>();
graph[edges[i][0]].add(edges[i][1]);
if(graph[edges[i][1]] == null)
graph[edges[i][1]] = new ArrayList<Integer>();
graph[edges[i][1]].add(edges[i][0]);
degree[edges[i][0]] ++;
degree[edges[i][1]] ++;
}
for(int i = 0; i < degree.length; i++) {
if(degree[i] == 0) return list;
if(degree[i] == 1) queue.offer(i);
}
while(!queue.isEmpty()) {
list = new ArrayList<Integer>();
int count = queue.size();
for(int i = 0; i < count; i++){
int tem = queue.poll();
list.add(tem);
degree[tem] --;
for(int v : graph[tem]) {
if(degree[v] == 0) continue;
if(degree[v] == 2) queue.offer(v);
degree[v] --;
}
}
}
return list;
}
}