對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱(chēng)為最小高度樹(shù)。給出這樣的一個(gè)圖，寫(xiě)出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。格式該圖包含 n 個(gè)節(jié)點(diǎn)，標(biāo)記為 0 到 n - 1。給定數(shù)字 n 和一個(gè)無(wú)向邊 edges 列表（每一個(gè)邊都是一對(duì)標(biāo)簽）。你可以假設(shè)沒(méi)有重復(fù)的邊會(huì)出現(xiàn)在 edges 中。由于所有的邊都是無(wú)向邊， [0, 1]和 [1, 0] 是相同的，因此不會(huì)同時(shí)出現(xiàn)在 edges 里。示例 1:輸入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]0|1/ \2 3 輸出: [1]

代碼

class Solution {public List<Integer> findMinHeightTrees(int n, int[][] edges) {Map<Integer,List<Integer>> map=new HashMap<>();for(int i=0;i<n;i++)map.put(i,new ArrayList<>());for (int[] edge:edges)//建立鄰接表{map.get(edge[0]).add(edge[1]);map.get(edge[1]).add(edge[0]);}boolean[] check=new boolean[n]; int[] degree=new int[n];Queue<Integer> queue=new LinkedList<>();for(int i=0;i<n;i++)//記錄節(jié)點(diǎn)的度，并且將度為1的節(jié)點(diǎn)入隊(duì)if (map.get(i).size()==1) {queue.add(i);check[i]=true;degree[i]=1;}else {degree[i]=map.get(i).size();}if(queue.isEmpty()) return new ArrayList<>(){{add(0);}};//沒(méi)有度為1的節(jié)點(diǎn)ArrayList<Integer> res=new ArrayList<>();while (!queue.isEmpty())//bfs{int size=queue.size();ArrayList<Integer> temp=new ArrayList<>();for(int i=0;i<size;i++){int cur=queue.poll();for(int c:map.get(cur))//移除當(dāng)前節(jié)點(diǎn)，將相鄰節(jié)點(diǎn)的度減去1{if(!check[c]){degree[c]--;if(degree[c]<=1)//度為1則入隊(duì){queue.offer(c);check[c]=true;}}}temp.add(cur);}res=temp;}return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode310. 最小高度树（bfs）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。