Foraundirectedgraphwithtreecharacteristics,wecanchooseanynodeastheroot.Theresultgraphisthenarootedtree.Amongallpossiblerootedtrees,thosewithminimumheightarecalledminimumheighttrees(MHTs).Givensuchagraph,writeafunctiontofindalltheMHTsandreturnalistoftheirrootlabels.
FormatThegraphcontainsnnodeswhicharelabeledfrom0ton-1.Youwillbegiventhenumbernandalistofundirectededges(eachedgeisapairoflabels).
Youcanassumethatnoduplicateedgeswillappearinedges.Sincealledgesareundirected,[0,1]isthesameas[1,0]andthuswillnotappeartogetherinedges.
Example1:
Input:n=4,edges=[[1,0],[1,2],[1,3]]0|1/\23Output:[1]
Example2:
Input:n=6,edges=[[0,3],[1,3],[2,3],[4,3],[5,4]]012\|/3|4|5Output:[3,4]
Note:
AccordingtothedefinitionoftreeonWikipedia:“atreeisanundirectedgraphinwhichanytwoverticesareconnectedbyexactlyonepath.Inotherwords,anyconnectedgraphwithoutsimplecyclesisatree.”Theheightofarootedtreeisthenumberofedgesonthelongestdownwardpathbetweentherootandaleaf.
找出以哪个节点为根节点时，树的高度最小。首先想到的方法可能是枚举每一个点为根，在查询高度。但是这种做法重复的操作数太多，时间复杂度高。因而有没有更好的算法去解决这个问题？先从这个根节点的特征下手。如果统计一下每个节点的入度，不难发现当节点的入度为1的时候，这个节点一定不会是最小高度树的根节点（n==1或n==2情况作为特殊情况判断）。排除了最外层的节点，那么所求的根节点必然在内部。对于没有分支的树所求的根节点就在内部，且处于对称中心最近的3和4节点。而推广到有分支的树时仍然时正确的。因此，问题转化为寻求距离树对称中心最近的节点。
我们也可以换一种更为直接的理解方式。要求树的高度，必然是从入度为1的节点出发，到当前假定的根节点，所经历的节点数即为以当前假定根节点为树的高度。因此我们可以从所有入度为1的节点出发，沿着给定的路径移动，直到相遇，或者彼此已经擦身而过一个节点的距离，此时的节点便是所求的最小高度树的根节点
classSolution{public:vector<int>findMinHeightTrees(intn,vector<pair<int,int>>&edges){vector<int>ans;if(n==1){ans.push_back(0);returnans;}if(edges.size()==0)returnans;vector<int>deg(n,0);vector<vector<int>>preHead(n);for(constauto&pos:edges){preHead[pos.first].push_back(pos.second);deg[pos.first]++;preHead[pos.second].push_back(pos.first);deg[pos.second]++;}set<int>vis;queue<int>Q;for(registerinti=0;i<n;i++)if(deg[i]==1){Q.push(i);vis.insert(i);}intnow;while(!Q.empty()&&n>2){intlen=Q.size();for(registerinti=0;i<len;i++){now=Q.front();Q.pop();for(autopos:preHead[now]){deg[pos]--;if(deg[pos]==1&&vis.find(pos)==vis.end()){Q.push(pos);vis.insert(pos);}}}n-=len;}while(!Q.empty()){ans.push_back(Q.front());Q.pop();}returnans;}};
