Java實現(xiàn)最小高度樹
題設(shè)要求
樹是一個無向圖,其中任何兩個頂點只通過一條路徑連接。 換句話說,一個任何沒有簡單環(huán)路的連通圖都是一棵樹。
給你一棵包含 n 個節(jié)點的樹,標記為 0 到 n - 1 。給定數(shù)字 n 和一個有 n - 1 條無向邊的 edges 列表(每一個邊都是一對標簽),其中 edges[i] = [ai, bi] 表示樹中節(jié)點 ai 和 bi 之間存在一條無向邊。
可選擇樹中任何一個節(jié)點作為根。當選擇節(jié)點 x 作為根節(jié)點時,設(shè)結(jié)果樹的高度為 h 。在所有可能的樹中,具有最小高度的樹(即,min(h))被稱為 最小高度樹 。
請你找到所有的 最小高度樹 并按 任意順序 返回它們的根節(jié)點標簽列表。
樹的 高度 是指根節(jié)點和葉子節(jié)點之間最長向下路徑上邊的數(shù)量。
示例 1:
輸入:n = 4, edges = [[1,0],[1,2],[1,3]]
輸出:[1]
解釋:如圖所示,當根是標簽為 1 的節(jié)點時,樹的高度是 1 ,這是唯一的最小高度樹。
示例 2:
輸入:n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
輸出:[3,4]
提示:
1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
給定的輸入保證是一棵樹,并且不會有重復(fù)的邊
解題思路
? 由上述兩個圖我們可以得出結(jié)論:題中需要求解的是樹里面的中心節(jié)點,而每個樹的中心節(jié)點不會超過兩個。
? 而我們想要求得樹里面的中心節(jié)點,我們就可以逐層FBS(也就是逐層將出度為一的葉子節(jié)點剪掉),直至剪到最后一層,就可以將結(jié)果輸出了!
算法
class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer> res = new ArrayList<Integer>(); //如果只有一個節(jié)點,則它就是最小高度樹 if(n == 1){ res.add(0); return res; } //每個節(jié)點的鄰居數(shù)量 int [] degree = new int[n]; //每個節(jié)點的鄰居 HashMap<Integer,List<Integer>> map = new HashMap<>(); for(int [] edge : edges){ int a = edge[0]; int b = edge[1]; degree[a]++; degree[b]++; if(map.get(a) == null){ map.put(a,new ArrayList<Integer>());//key:節(jié)點 value:鄰居 } if(map.get(b) == null){ map.put(b,new ArrayList<Integer>());//key:節(jié)點 value:鄰居 } map.get(a).add(b); map.get(b).add(a); } //建立隊列 LinkedList<Integer> leafNodes = new LinkedList<Integer>();//表示葉子節(jié)點 //將所有度為1的節(jié)點入隊 for(int i = 0;i < degree.length;i++){ if(degree[i] == 1){ leafNodes.add(i); } } while(leafNodes.size() > 0){ res.clear(); //每一層節(jié)點的數(shù)量 int size = leafNodes.size(); for(int i = 0;i < size;i++){ int leaf = leafNodes.poll(); //將當前節(jié)點加入到結(jié)果集 res.add(leaf); List<Integer> neighbors = map.get(leaf); //將出度減一,也就是將最外層的葉子節(jié)點剪掉 for(int neighbor : neighbors){ degree[neighbor]--; if(degree[neighbor] == 1){ //葉子節(jié)點入隊 leafNodes.add(neighbor); } } } } return res; } }
到此這篇關(guān)于Java實現(xiàn)最小高度樹的文章就介紹到這了,更多相關(guān)Java 最小高度樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
SpringBoot中實現(xiàn)定時任務(wù)的幾種方式
定時任務(wù)在我們項目開發(fā)中也是很重要的,對于某些場景必須要用定時任務(wù)?,如定時發(fā)送郵件啊,定時統(tǒng)計數(shù)據(jù)等,這篇文章主要講講項目中實現(xiàn)定時任務(wù)的幾種方式,需要的朋友可以參考下2023-05-05Spring boot實現(xiàn)一個簡單的ioc(1)
這篇文章主要為大家詳細介紹了Spring boot實現(xiàn)一個簡單的ioc,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-04-04解決mybatis-plus動態(tài)數(shù)據(jù)源切換不生效的問題
本文主要介紹了解決mybatis-plus動態(tài)數(shù)據(jù)源切換不生效的問題,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01詳解springboot設(shè)置cors跨域請求的兩種方式
這篇文章主要介紹了詳解springboot設(shè)置cors跨域請求的兩種方式,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-11-11Spring Cloud Gateway重試機制的實現(xiàn)
這篇文章主要介紹了Spring Cloud Gateway重試機制的實現(xiàn),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2019-03-03