leetcode 310. Minimum Height Trees

本文主要是介绍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;
}
};