題目鏈接
最小高度樹
思路：本質上是找到樹中的最長路徑。當最長路徑上中間點（若路經長為偶數，則中間點僅有一個，否者中間點有兩個）作為根時，此時樹高最小。
Code:
class Solution {
public://拓撲排序int d[20010];queue<pair<int,int>> q;vector<int> e[20010];bool vis[20010];vector<pair<int,int>> res;vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {vector<int> ans;if(n==1) {ans.push_back(0);return ans;}for(int i=0;i<edges.size();i++) {e[edges[i][0]].push_back(edges[i][1]);e[edges[i][1]].push_back(edges[i][0]);d[edges[i][0]]++;d[edges[i][1]]++;}for(int i=0;i<n;i++) {if(d[i]==1) {q.push({i,0});res.push_back({0,i});vis[i] = 1;}}while(q.size()) { //bfsint k = q.front().first;int dis = q.front().second;q.pop();for(int i=0;i<e[k].size();i++) {d[e[k][i]]--;if(d[e[k][i]] == 1 && !vis[e[k][i]]) {q.push({e[k][i],dis+1});res.push_back({dis+1,e[k][i]});vis[e[k][i]] = 1;}}}sort(res.begin(),res.end());ans.push_back(res[n-1].second);if(res[n-1].first == res[n-2].first) ans.push_back(res[n-2].second);return ans;}
};
)
)
