# 624 ms C++ beats 100%

• ``````// root of MHT must locate at the middle point of the tree
// Let's start from leaves, the points with only one edge. Remove all leaves.
// Then, we will get new leaves, remove all of them again and again like peeling an apple.
// eventually , we will get only one point (the root of MHT) or one edge (these two points are the roots of MHT)

class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> out;

int ne=edges.size();
if(n==1){   // one node , MHT size==1 rooted at node 0
out.push_back(0);
return out;
}
for(int i=0;i<ne;i++){  // build up adjacency list
e[edges[i].first].push_back(edges[i].second);
e[edges[i].second].push_back(edges[i].first);
}

while(ne>1){
queue<int> ends;
for(int i=0;i<n;i++){   //push all leaves of pre-peeled tree to queue
if(e[i].size()==1){
ends.push(i);
}
}
if(ne==ends.size()){    // i.e. , after peeling , all edges will be gone so the intersection of these edges is the root
out.push_back(e[ends.front()].front());
return out;
}
while(!ends.empty()){   // peeling the leaves

ne--;   // update current edge size
int end1=ends.front();  // end point of a leaf
int end2=e[end1].front();   // the edged point with this leaf
ends.pop();
for(auto it=e[end2].begin();it!=e[end2].end();it++){
if(*it==end1) {
break;
}
}

}
}
// after while loop , only one edge left which contains two roots of MHTs

for(int i=0;i<n;i++){
if(e[i].size()==1){
out.push_back(i);
out.push_back(e[i].front());
break;
}
}
return out;
}
``````

};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.