Leetcode: 310.Minimum Height Trees

继续是图的题目。这道题首先介绍了一下无环的无向图是可以转为树的（嗯，不一定是二叉树，可以是有多个子树的那种树）。然后给出一个无环无向图，求该无向图转化为的所有树中最小高度的树的最小高度。

呐，按照题意的意思呢，就是一个遍历的题目了。一开始大概的想法是遍历所有子树，再求出所有子树的高度，最后一比较，答案就有了。这样的复杂度大概是O(n^2)。复杂度有点大了，而且实现起来有点复杂。

从找规律入手，最小高度意味着它有很多的子树，而且每颗子树都基本是平衡的。如果每次都去除当前的叶子，那么剩到最后的就是拥有最小高度的子树的根了。大概的逻辑如下： - 把当前所有的叶子删除，新叶子存起来 - 一轮一轮进行，直到还剩一个根或者两个根结点

经夜少提醒，该种排序历遍的思想是拓扑排序 维护一个入度为0的集合。每次提取其中一个顶点，并把由它引出的所有边遍历，逐一调整剩下顶点的入度，并把新一轮的入度为0的点加进集合。这样“最后一层”入度为0的结点即为所求。拓扑排序是这样一种排序，希望求得一个排序，使得排在A后的所有顶点都有一条A到他们的路，而排在A前的，都不存在一条路从A出发到达他们。所以也是要求无环的。

代码

结构选择： - graphs用来存图，需要存一个label和对应的邻接表。因为这里是label是顺序的且唯一的，可以用vector或者unordered_map，邻接表可以用vector或者unordered_set，就查询结点来看，vector或者unordered_map都可以满足要求，因为后面要对邻接表进行删除操作，所以选择unordered_set - leaf用来存当前轮的叶子，因为要按顺序删除，用了先进先出的queue，其实后进后出的vector也可以，因为同一轮的叶子没有先后之分 - leaf用来存剩下的结点数，因为想要快速删除，所以用了unordered_set

#include <iostream> #include <unordered_map> #include <vector> #include <unordered_set> #include <queue> using namespace std; vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { unordered_map<int,unordered_set<int>> graphs; unordered_set<int> left; queue<int> leaf; vector<int> ans; for(auto it : edges) { graphs[it.first].insert(it.second); graphs[it.second].insert(it.first); } for(int i =0; i<n; i++) { left.insert(i); if(graphs[i].size() == 1) leaf.push(i); } while(1) { queue<int> temp; int p; if(left.size() <= 2) break; while(!leaf.empty()) { p = leaf.front(); leaf.pop(); left.erase(p); for(auto neigh : graphs[p]) { graphs[neigh].erase(p); if(graphs[neigh].size()==1) temp.push(neigh); } } leaf = temp; } for(auto i : left) { ans.push_back(i); cout<<i<<endl; } return ans; } int main() { int n=6; vector<pair<int,int>> edges; edges.push_back(make_pair(0,3)); edges.push_back(make_pair(1,3)); edges.push_back(make_pair(2,3)); edges.push_back(make_pair(4,3)); edges.push_back(make_pair(5,4)); findMinHeightTrees(n,edges); cout << "Hello world!" << endl; return 0; }

拓展

这次尝试把代码写得简单些，用了c++11的一些特性。比如基于范围的for需要注意的是，for(auto a : b)这种形式中，b应该是一种数据结构，比如vector，char[]之类的，而且得到的a不会是指针，而直接是解引用后的内容，非常方便。auto在写iterator一类的长类型的时候很好用。

set的底层是一个搜索二叉树，所以内部是已经排序了的。用于做循环的时候如果要对里面做insert或者erase操作很危险。