Leetcode 310. Minimum Height Trees

xuxueli 發(fā)布于2019-08-14 17:11 / 1551人閱讀

摘要：可以從頭邊同時進(jìn)行，查看葉子節(jié)點(diǎn)并加入到葉子節(jié)點(diǎn)鏈表遍歷一遍后，葉子節(jié)點(diǎn)鏈表為。將葉子節(jié)點(diǎn)保存下來。這個時候就會有第二層葉子節(jié)點(diǎn)那些在列表當(dāng)中為的點(diǎn)，用同樣的方法進(jìn)行剝除。最后留在葉子節(jié)點(diǎn)里面的點(diǎn)即可以為根。

題目：

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.

解法：
因?yàn)闃渚褪莾蓚€點(diǎn)被一條線鏈接的無向圖，所以先用一個list把樹存成無向圖的列表。可以從頭邊同時進(jìn)行，查看葉子節(jié)點(diǎn)并加入到葉子節(jié)點(diǎn)鏈表（遍歷一遍后，葉子節(jié)點(diǎn)鏈表size 為1）。將葉子節(jié)點(diǎn)保存下來。這些葉子節(jié)點(diǎn)不用再查，但是剩余的中間節(jié)點(diǎn)，要依次查看，把跟第一層葉子節(jié)點(diǎn)有關(guān)的圖的矩陣?yán)飳?yīng)的記錄全部刪除，類似于剝除最外面一圈所有的點(diǎn)。這個時候就會有第二層葉子節(jié)點(diǎn)（那些在列表當(dāng)中size為1的點(diǎn)），用同樣的方法進(jìn)行剝除。最后留在葉子節(jié)點(diǎn)list里面的點(diǎn)即可以為根。

代碼：

public List findMinHeightTrees(int n, int[][] edges) {
        List leaves = new ArrayList<>();
        if (n == 1) {
            leaves.add(0);
            return leaves;
        }
        
        List> adj = new ArrayList<>();
        for(int i = 0; i < n; i++) adj.add(new HashSet<>());
        for(int[] edge : edges){
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        for(int i = 0; i < n; i++) 
         if(adj.get(i).size()==1) leaves.add(i);
        while(n > 2){
            n-=leaves.size();
            List newLeaves = new ArrayList<>();
            for(int i : leaves){
                for(int j : adj.get(i)){
                    adj.get(j).remove(i);
                    if(adj.get(j).size() ==1) newLeaves.add(j);
                }
            }
            leaves = newLeaves;
        }
        return leaves;
    }