資訊專欄INFORMATION COLUMN
摘要：圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱為最小高度樹(shù)。給出這樣的一個(gè)圖，寫(xiě)出一個(gè)函數(shù)找到所有的最小高度樹(shù)并返回他們的根節(jié)點(diǎn)。因此使用一個(gè)數(shù)組代表每個(gè)節(jié)點(diǎn)的入度，若入度為就是葉子節(jié)點(diǎn)。
題目地址：
https://leetcode-cn.com/probl...
題目描述：
對(duì)于一個(gè)具有樹(shù)特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹(shù)，在所有可能的樹(shù)中，具有最小高度的樹(shù)被稱為最小高度樹(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]
示例 2:
輸入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
| /
3
|
4
|
5
輸出: [3, 4]
解答：
這一題比較有技巧，如果求任意一點(diǎn)到任意一點(diǎn)的距離，那么會(huì)時(shí)間復(fù)雜度會(huì)很大。
比較高效的做法是，每次把葉子節(jié)點(diǎn)從圖(把樹(shù)轉(zhuǎn)換為圖結(jié)構(gòu))刪掉。
直到只剩下1個(gè)或者2個(gè)點(diǎn)的時(shí)候輸出。
算法思想很簡(jiǎn)單。但是實(shí)現(xiàn)起來(lái)有寫(xiě)麻煩。如果每次都判斷葉子節(jié)點(diǎn)，那么效率會(huì)很低。
因此使用一個(gè)數(shù)組inDegree[]代表每個(gè)節(jié)點(diǎn)的入度，若入度為1就是葉子節(jié)點(diǎn)。
并且用一個(gè)隊(duì)列(棧也可以，只要是那種能彈出的容器即可)裝葉子節(jié)點(diǎn)。
然后寬度優(yōu)先搜索隊(duì)列中葉子節(jié)點(diǎn)，刪除節(jié)點(diǎn)和它們對(duì)應(yīng)的邊，并加入新的葉子節(jié)點(diǎn)(有可能刪除葉子節(jié)點(diǎn)的邊之后，它的鄰接點(diǎn)p的入度變?yōu)?,也就是inDegree[p] = 1，此時(shí)可以把p加入隊(duì)列中)。
直到只剩下1個(gè)或者2個(gè)點(diǎn)停止。返回結(jié)果。
java ac代碼：
class Solution {
public List findMinHeightTrees(int n, int[][] edges) {
Listans = null;
if(n <= 2)
{
ans = new ArrayList(2);
for(int i = 0;i < n;i++)
ans.add(i);
return ans;
}
//去掉葉子節(jié)點(diǎn)，直到只剩下一個(gè)或者兩個(gè)節(jié)點(diǎn)。
int[]inDegree = new int[n];
//用鄰接表存儲(chǔ)圖。
List[] 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;
Queuequeue = 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;
}
}
這個(gè)和力扣(LeetCode)207很像，雖然不是拓?fù)渑判?，但都是利用一個(gè)可彈出容器裝節(jié)點(diǎn)，然后寬度搜索容器中的節(jié)點(diǎn)。
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/73973.html
摘要：關(guān)于遞歸這里提一兩點(diǎn)遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡(jiǎn)介：大家好，我是車神哥，府學(xué)路18號(hào)的車神? ?個(gè)人主頁(yè)：應(yīng)無(wú)所住而生...
摘要：對(duì)于每個(gè)氣球，提供的輸入是水平方向上，氣球直徑的開(kāi)始和結(jié)束坐標(biāo)?？梢陨涑龅墓臄?shù)量沒(méi)有限制。弓箭一旦被射出之后，可以無(wú)限地前進(jìn)。我們想找到使得所有氣球全部被引爆，所需的弓箭的最小數(shù)量。解答這是一道區(qū)間覆蓋問(wèn)題，不太好說(shuō)清楚，利用模板即可。 題目地址：https://leetcode-cn.com/probl...題目描述：在二維空間中有許多球形的氣球。對(duì)于每個(gè)氣球，提供的輸入是水平方...
摘要：有效二叉搜索樹(shù)定義如下節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)。而我們二叉搜索樹(shù)保證了左子樹(shù)的節(jié)點(diǎn)的值均小于根節(jié)點(diǎn)的值，根節(jié)點(diǎn)的值均小于右子樹(shù)的值，因此中序遍歷以后得到的序列一定是升序序列。 ...
摘要：提示節(jié)點(diǎn)數(shù)介于到之間。無(wú)向圖是一個(gè)簡(jiǎn)單圖，這意味著圖中沒(méi)有重復(fù)的邊，也沒(méi)有自環(huán)。必須將給定節(jié)點(diǎn)的拷貝作為對(duì)克隆圖的引用返回。這一題的做法是，使用一個(gè)來(lái)記錄，原和新的對(duì)應(yīng)關(guān)系。 題目地址：https://leetcode-cn.com/probl...題目描述：給定無(wú)向連通圖中一個(gè)節(jié)點(diǎn)的引用，返回該圖的深拷貝（克?。D中的每個(gè)節(jié)點(diǎn)都包含它的值 val（Int） 和其鄰居的列表（list...
閱讀 1775·2021-11-22 12:09
閱讀 1479·2019-08-30 13:22
閱讀 2110·2019-08-29 17:00
閱讀 2657·2019-08-29 16:28
閱讀 2974·2019-08-26 13:51
閱讀 1201·2019-08-26 13:25
閱讀 3260·2019-08-26 12:14
閱讀 3031·2019-08-26 12:14
