脚本宝典收集整理的这篇文章主要介绍了Minimum Height Trees,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
Minimum Height Trees
题目链接:https://leetcode.com/problems...
图的题,和course schedule差不多。bfs来解,每次放入只有一个edge的node(现在的leaf)。然后直到只剩最上面一层。注意考虑单独的node(和别的node不相连)。比如: [[1,2], [2,3]], n = 6这种情况,就有[0, 4, 5]三个点都不和别的node相连。还有[], n = 2的时候就要返回[0, 1]。
public class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// adjacent set
Set<Integer>[] set = new HashSet[n];
for(int i = 0; i < n; i++) set[i] = new HashSet();
for(int[] edge : edges) {
set[edge[0]].add(edge[1]);
set[edge[1]].add(edge[0]);
}
// use queue to do bfs
LinkedList<Integer> q = new LinkedList();
List<Integer> edge_case = new ArrayList();
for(int i = 0; i < set.length; i++) {
if(set[i].size() == 1) q.add(i);
if(set[i].size() == 0) edge_case.add(i);
}
// if cycle
if(q.size() == 0) return edge_case;
int count = edge_case.size();
while(count + q.size() < n) {
int size = q.size();
count += size;
while(size-- > 0) {
int node = q.remove();
int parent = set[node].iterator().next();
set[node].remove(parent);
set[parent].remove(node);
if(set[parent].size() == 1) q.add(parent);
}
}
return q;
}
}
以上是脚本宝典为你收集整理的Minimum Height Trees全部内容,希望文章能够帮你解决Minimum Height Trees所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。