正文
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,
[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]
分析：
首先笨办法，假设每个点都是root, 然后利用BFS，看那个root到最后一个leaf的高度是多少，如果比目前找到的更小，则更新，如果相同，则把那个点加到list里。
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> all = new ArrayList<Integer>();
if (n <= ) {
all.add();
return all;
}
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = ; i < n; i++) {
map.put(i, new ArrayList<Integer>());
}
for (int[] edge : edges) {
map.get(edge[]).add(edge[]);
map.get(edge[]).add(edge[]);
}
int minHeight = Integer.MAX_VALUE;
List<Integer> temp = new ArrayList<>();
for (int i = ; i < n; i++) {
int height = ;
boolean[] visited = new boolean[n];
visited[i] = true;
List<Integer> list = map.get(i);
while (list.size() != ) {
for (Integer k : list) {
if (!visited[k]) {
visited[k] = true;
temp.addAll(map.get(k));
}
}
list = temp;
temp = new ArrayList<>();
height++;
}
if (height < minHeight) {
all.clear();
all.add(i);
minHeight = height;
} else if (height == minHeight) {
all.add(i);
}
}
return all;
}
更好的方法，先构成一棵树，把数的叶子逐层的砍掉（叶子的degree为1），当这棵树只剩下2颗或者不到两颗的节点的时候，就停止。
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> leaves = new ArrayList<Integer>();
if (n <= ) {
leaves.add();
return leaves;
}
List<Set<Integer>> graph = new ArrayList<>();
for (int i = ; i < n; i++) {
graph.add(new HashSet<Integer>());
}
for (int[] edge : edges) {
graph.get(edge[]).add(edge[]);
graph.get(edge[]).add(edge[]);
}
for (int i = ; i < n; i++) {
if (graph.get(i).size() == ) {
leaves.add(i);
}
}
while (n > ) {
n -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int leave : leaves) {
for (int newLeaf : graph.get(leave)) {
graph.get(newLeaf).remove(leave);
if (graph.get(newLeaf).size() == ) {
newLeaves.add(newLeaf);
}
}
}
leaves = newLeaves;
}
return leaves;
}
}
