力扣(LeetCode)310
題目地址:
https://leetcode-cn.com/probl...
題目描述:
對於一個具有樹特徵的無向圖,我們可選擇任何一個節點作為根。圖因此可以成為樹,在所有可能的樹中,具有最小高度的樹被稱為最小高度樹。給出這樣的一個圖,寫出一個函式找到所有的最小高度樹並返回他們的根節點。 格式 該圖包含 n 個節點,標記為 0 到 n - 1。給定數字 n 和一個無向邊 edges 列表(每一個邊都是一對標籤)。 你可以假設沒有重複的邊會出現在 edges 中。由於所有的邊都是無向邊, [0, 1]和 [1, 0] 是相同的,因此不會同時出現在 edges 裡。 示例 1: 輸入: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 23 輸出: [1] 示例 2: 輸入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] 012 \ | / 3 | 4 | 5 輸出: [3, 4]
解答:
這一題比較有技巧,如果求任意一點到任意一點的距離,那麼會時間複雜度會很大。
比較高效的做法是,每次把葉子節點從圖(把樹轉換為圖結構)刪掉。
直到只剩下1個或者2個點的時候輸出。
演算法思想很簡單。但是實現起來有寫麻煩。如果每次都判斷葉子節點,那麼效率會很低。
因此使用一個數組inDegree[]代表每個節點的入度,若入度為1就是葉子節點。
並且用一個佇列(棧也可以,只要是那種能彈出的容器即可)裝葉子節點。
然後寬度優先搜尋隊列中葉子節點,刪除節點和它們對應的邊,並加入新的葉子節點(有可能刪除葉子節點的邊之後,它的鄰接點p的入度變為1,也就是inDegree[p] = 1,此時可以把p加入佇列中)。
直到只剩下1個或者2個點停止。返回結果。
java ac程式碼: class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer>ans = null; if(n <= 2) { ans = new ArrayList(2); for(int i = 0;i < n;i++) ans.add(i); return ans; } //去掉葉子節點,直到只剩下一個或者兩個節點。 int[]inDegree = new int[n]; //用鄰接表儲存圖。 List<Integer>[] map = new List[n]; for(int i = 0;i < n;i++) map[i] = new ArrayList(); for(int i = 0;i < edges.length;i++) { map[edges[i][0]].add(edges[i][1]); map[edges[i][1]].add(edges[i][0]); inDegree[edges[i][0]]++; inDegree[edges[i][1]]++; } int count = n; Queue<Integer>queue = new ArrayDeque(); for(int i = 0;i < n;i++) if(inDegree[i] == 1) queue.offer(i); while(count > 2) { int size = queue.size(); for(int loc= 0;loc < size;loc++) { int ii = queue.poll(); int jj = map[ii].get(0); inDegree[jj]--; if(inDegree[jj] == 1) queue.offer(jj); map[jj].remove(new Integer(ii)); map[ii].remove(new Integer(jj)); inDegree[ii] = -1; count--; } } ans = new ArrayList(queue); return ans; } }
這個和力扣(LeetCode)207很像,雖然不是拓撲排序,但都是利用一個可彈出容器裝節點,然後寬度搜索容器中的節點。