# 310 - Minimum Height Trees

## 解法一 - Topological Sort

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<int> minHeightTrees;
if (n <= 0) {
return minHeightTrees;
}

if (n == 1) {
minHeightTrees.push_back(0);
return minHeightTrees;
}

// Build the graph
unordered_map<int, int> inDegree;
unordered_map<int, vector<int>> graph;
for(auto& edge: edges) {
int n1 = edge[0];
int n2 = edge[1];

graph[n1].push_back(n2);
graph[n2].push_back(n1);
++inDegree[n1];
++inDegree[n2];
}

// Get the leaves
deque<int> leaves;
for(auto& p: inDegree) {
if(p.second == 1) {
leaves.push_back(p.first);
}
}

// Remove leaves until there are less than two nodes left
int totalNodes = n;
while(totalNodes > 2) {
int leavesSize = leaves.size();
totalNodes -= leavesSize;

for (int i = 0; i < leavesSize; i++) {
int vertex = leaves.front();
leaves.pop_front();

for (auto& child : graph[vertex]) {
if (--inDegree[child] == 1) {  // if the child has become a leaf
leaves.push_back(child);
}
}
}
}

// return the nodes left

move(begin(leaves), end(leaves), back_inserter(minHeightTrees));
return minHeightTrees;
}
};
``````