題目

樹是一個無向圖，其中任何兩個頂點只通過一條路徑連接。 換句話說，任何一個沒有簡單環路的連通圖都是一棵樹。

給你一棵包含?n?個節點的樹，標記為?0?到?n - 1?。給定數字?n?和一個有?n - 1?條無向邊的?edges?列表（每一個邊都是一對標簽），其中?edges[i] = [ai, bi]?表示樹中節點?ai?和?bi?之間存在一條無向邊。

可選擇樹中任何一個節點作為根。當選擇節點?x?作為根節點時，設結果樹的高度為?h?。在所有可能的樹中，具有最小高度的樹（即，min(h)）被稱為?最小高度樹?。

請你找到所有的?最小高度樹?并按?任意順序?返回它們的根節點標簽列表。

樹的?高度?是指根節點和葉子節點之間最長向下路徑上邊的數量。

示例 1：

輸入：n = 4, edges = [[1,0],[1,2],[1,3]]
輸出：[1]
解釋：如圖所示，當根是標簽為 1 的節點時，樹的高度是 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)?互不相同
• 給定的輸入?保證?是一棵樹，并且?不會有重復的邊

思路

????????我們可以通過樹的直徑特性來尋找最小高度樹的根節點。我們可以先找到樹中兩個最遠節點之間的路徑，通過dfs可以確定樹的直徑,先從任意節點出發找到最遠節點x，再從x出發找到最遠節點y，路徑x-y就是樹的直徑，然后通過回溯路徑找到直徑的中心節點，如果直徑長度為奇數，中心為中間一個節點，如果為偶數，中心為中間兩個節點。

代碼

class Solution {
public://更新所有節點到u的距離dist和父節點parentvoid dfs(int u, vector<int> & dist, vector<int> & parent, const     vector<vector<int>> & a) {for (size_t i=0;i<a[u].size();i++){int v=a[u][i];if (dist[v]<0)//鄰居v未被訪問{dist[v]=dist[u]+1;//更新距離parent[v]=u;//記錄父節點dfs(v,dist,parent,a);//遞歸訪問v}}}//從節點u出發,找到距離u最遠的節點,并返回該節點的編號int ll(int u,vector<int> &parent,const vector<vector<int>> &a){int n=a.size();vector<int> dist(n,-1);dist[u]=0;dfs(u,dist,parent,a);//更新距離和父節點int maxdist=0;int node=-1;for (int i=0;i<n;i++){if(dist[i]>maxdist){maxdist=dist[i];node=i;}}return node;}vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if (n==1){return {0};}vector<vector<int>> a(n);//存每個節點的鄰居for (auto &edge:edges){a[edge[0]].emplace_back(edge[1]);a[edge[1]].emplace_back(edge[0]);}vector<int> parent(n, -1);//找到距離節點0最遠的節點xint x=ll(0,parent,a);//找到距離節點x最遠的節點yint y=ll(x,parent,a);//找到節點x到節點y的路徑vector<int> path;parent[x]=-1;while(y!=-1)//從節點y開始,沿著parent數組回溯到x，得到路徑path{path.emplace_back(y);//存儲的是從y到x的路徑y=parent[y];}int m=path.size();if (m%2==0)//兩個節點{return {path[m/2-1],path[m/2]};}else//一個節點{return {path[m/2]};}}
};