# [recommend for beginners]clean C++ implementation with detailed explanation

• My implementation just follows the idea that the-path-method inspired from

http://algobox.org/minimum-height-trees/

Just like topological sorting, we delete the in-degree-1-node level by level.

Just we can ensure that the path of the longest length will be left.

So the last 1 or last 2 node is the solution

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> result;
if(n==1) { result.push_back(0); return result; }
vector<unordered_set<int>> graph(n, unordered_set<int>());
for(int i=0; i<edges.size(); i++){
graph[edges[i].first].insert(edges[i].second);
graph[edges[i].second].insert(edges[i].first);
}
vector<int> degree(n, 0);
for(int i=0; i<n; i++){
degree[i]=graph[i].size();
cout<<i<<":"<<degree[i]<<endl;
}
int count=n;
while(count>2){
vector<int> record;
for(int i=0; i<n; i++){
if(degree[i]==1) {
count--;
degree[i]=-1;
record.push_back(i);
}
}
for(int i=0; i<record.size(); i++){
for(auto it : graph[record[i]])  degree[it]--;
}
}
for(int i=0; i<n; i++){
if(degree[i]==1 || degree[i]==0)  result.push_back(i);
}
return result;
}
};
``````

• ``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
vector<int> in_degree(n, 0);
unordered_map<int, vector<int>> graph;
for(auto edge : edges) {
in_degree[edge.first]++;
in_degree[edge.second]++;
graph[edge.first].push_back(edge.second);
graph[edge.second].push_back(edge.first);
}

/*** store the in-degree=1 node **/
int count = n;
int level = 0;
/** bug **/

while(count > 2) {
level++;
vector<int> can_set;
for(int i = 0; i < n; i++) {
if(in_degree[i] == 1) {
in_degree[i] = -1;
can_set.push_back(i);
count--;
}
}
for(auto it : can_set) {
for(auto neighbor : graph[it]) {
in_degree[neighbor]--;
}
}
}

vector<int> result;
for(int i=0; i<n; i++) {
if(in_degree[i] == 0 || in_degree[i] == 1) {
result.push_back(i);
}
}
return result;
}
};``````

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