题目来源
给一个图，求一个根节点使得这棵树的高度最低。
头还有点晕…感觉不能思考…这道题怎么做，看了tags还是不懂。
看看讨论区吧。
主要是一个广度优先搜索的思想，设置多个指针，从叶子节点往里遍历，直到最后只剩下俩指针指向同一个节点或者相差一个节点。
代码如下：
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1)
return vector<int>{0};
unordered_map<int, unordered_set<int>> adj;
for (auto edge : edges) {
adj[edge.first].insert(edge.second);
adj[edge.second].insert(edge.first);
}
vector<int> leaves;
for (auto item : adj) {
if (item.second.size() == 1)
leaves.push_back(item.first);
}
while (n > 2) {
n -= leaves.size();
vector<int> newLeaves;
for (auto leaf : leaves) {
int nextNode = *adj[leaf].begin();
adj[leaf].erase(nextNode);
adj[nextNode].erase(leaf);
if (adj[nextNode].size() == 1)
newLeaves.push_back(nextNode);
}
leaves = newLeaves;
}
return leaves;
}
};
