脚本宝典收集整理的这篇文章主要介绍了

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]。

clipboard.png

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群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过