本文主要是介绍leetcode 310. Minimum Height Trees，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目是给了一个图，求把某个节点提起来后，形成的树的高度最小。
第一个想法就是暴力搜索。
把每个点提起来，然后计算并对比树的高度。
结果就是超时。
优化了一些，发现还是没有办法在规定时间内处理完。
看了网上的大神huifeng guan和残酷刷题群之前的解法，觉得自己太low了。
既然题目要求提起某个节点后树的高度最小，问题转换下就是某个节点提起来后到其余的每个节点的距离最短。
我的高中的楼布局就是和这道题的图差不多，高一在北美的楼，高二，高三实验楼，教师楼，音乐，体育馆。都是互相通过楼梯链接一起。
我们的这个问题就好比安排高中教导主任的办公室一样，要找个合适的位置。这样可以迅速的到达战场。
那这个问题就简单一些了，把教导主任的办公室安排到所有楼里最中心的那个楼。
第一个例子就可以看到，把教导主任安排在1的位置就能第一时间到达战场。
对于第二个例子
想找到最核心的位置就得用到剥洋葱的办法，一层皮一层皮的剥。
先剥掉最外面一层洋葱（楼）， 也就是5， 0， 1， 2 这些最外面的洋葱（楼），然后就剩下3,4.
这两个楼就没有办法再剥了，再剥就连教导主任的存在都可以省掉了。
这样的话，把教导主任随意安排到3或者4号楼就行了。
用拓扑排序从最外面开始剥皮，剥到最后一层。留下来的就是答案了。
class Solution {
public:
unordered_map<int ,vector<int>> buildGraphic(vector<vector<int>>& edges)
{
unordered_map<int ,vector<int>> neighbors;
for(auto edge: edges)
{
neighbors[edge[0]].push_back(edge[1]);
neighbors[edge[1]].push_back(edge[0]);
}
return neighbors;
}
unordered_map<int, int> buildDegree(unordered_map<int ,vector<int>> neighbors){
unordered_map<int, int> degree;
for(auto neighbor: neighbors){
degree[neighbor.first] = neighbor.second.size();
}
return degree;
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
//build graphic
//set every node as root node and using bfs go through the tree level by level.
//push the root if the levels is min.
vector<int> ret;
if(edges.size() ==0 && n !=0)
for(int i=0;i<n;i++)
ret.push_back(i);
unordered_map<int ,vector<int>> neighbors = buildGraphic(edges);
unordered_map<int, int> degrees = buildDegree(neighbors);
unordered_set<int> accessed;
queue<int> myqueue;
//push the most out building into the queue
for(auto degree: degrees) {
if(degree.second == 1)
myqueue.push(degree.first);
}
while(!myqueue.empty()) {
ret.clear();
int size = myqueue.size();
for(int i=0;i<size;i++) {
int cur=myqueue.front();
myqueue.pop();
ret.push_back(cur);
for(auto neighbor: neighbors[cur]){
degrees[neighbor]--;
if(degrees[neighbor] == 1)
myqueue.push(neighbor);
}
}
}
return ret;
}
};
这篇关于leetcode 310. Minimum Height Trees的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
