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.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

return [3, 4]

Show Hint How many MHTs can a graph have at most? Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other Words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

s思路: 1. 提示很重要。不看的時候，只想到了簡單粗暴的方法。能不能先遍歷，找到最長的path的長度，如果長度為奇數(shù)，則只有一個root，即：path的中點是minimum height tree的root；如果長度是偶數(shù)，則有兩個,在path中間。 2. 如何快速找到最長的path呢？需要每個位置為root分別遍歷嗎？如果這樣的話，復(fù)雜度就是o(V(V+E))。但，潛意識感覺這樣有很多重復(fù)運算。 3. 剛想了一個方法：不用全部遍歷，而是先從任意節(jié)點開始，做bfs,看最后一層節(jié)點的個數(shù)，如果只有一個，表示從這個節(jié)點就可以找到最長的path;如果大于一個，那么從其中任一節(jié)點都可以得到最長path， 然后再遍歷一次，給每個節(jié)點標記層次數(shù)，最后找出符合要求的層數(shù)數(shù)中的節(jié)點輸出即可！這樣一來，復(fù)雜度就是o(v+e). 4. 要做兩次遍歷，還是不方便，不簡潔。看了以前的答案，還是用的經(jīng)典的bfs檢查cycle的方法，記錄degree，由于這里是undirected graph,所以沒有入度和出度一說，直接統(tǒng)計每個節(jié)點有幾個neighbor。由于已知是沒有cycle,那么統(tǒng)計了degree的好處是可以從圖的邊緣入手去找root，把所有的degree=1的點放在queue,然后每次從queue取出節(jié)點，把這些節(jié)點的鄰居節(jié)點的degree減一，如果減一后也碰巧等于１，說明去掉這條邊，其鄰居也成了新的邊界。如此這般，知道n==2或小于2，此時queue里面剩下的就是中心了。 5. 為什么bfs+統(tǒng)計degree可以辦到這件事呢？也就是說圖的問題很多都可以用bfs+統(tǒng)計degree的放法是為什么？原因，我覺得應(yīng)該是這種方法可以從結(jié)構(gòu)上結(jié)構(gòu)圖，剖析圖，把圖的性質(zhì)給顯露出來。比如這道題，求最小height，但height又是最長路徑，所以從結(jié)構(gòu)入手，就從leaf入手，而degree=1的節(jié)點就是leaf,從leaf入手一步一步反推就可以到root 6. 換個思路，我自己想的思路是從root開始做bfs，發(fā)現(xiàn)至少都要做兩次bfs，有重復(fù)之嫌；從相反角度考慮，從leaf入手，就簡單一些，而從leaf入手對bfs來說恰好有這個方法：統(tǒng)計入度或度。換個角度看問題而已，無所謂誰好誰壞，提供多角度的原因只是試圖還原事物的本來面部，或者試圖從多個角度來看事物。如果只看到一個角度，那一定是人偏執(zhí)的認為只有一個角度，或這某個角度比其他角度好！