Minimum Height Trees
For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph containsn
nodes which are labeled from0
ton - 1
. You will be given the numbern
and a list of undirectededges
(each edge is a pair of labels).
You can assume that no duplicate edges will appear inedges
. Since all edges are undirected,[0, 1]
is the same as[1, 0]
and thus will not appear together inedges
.
Example
Example 1 :
Example 2 :
Note
使用类似拓扑排序的思路进行解题。
关键是要注意到这是一个无向图的问题,我们需要从外层向内部进行遍历,基于入度进行排序,一层一层把叶子删去,更新下一层的入度,进队列,最后剩下的节点就是答案
入度这里指的是联通性,最低是1,我们从1开始“删除”
Code
Last updated