# 310 - Minimum Height Trees
解法一 - Topological Sort
上面的解法寫得滿清楚的,因為最後的答案就是整個 graph 最核心的那個或兩個 node,所以我們可以利用 topological sort 的概念,一直移除掉只有一條邊連接的 leaf node,實作如下:
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;
}
};
Last updated