leetcode Minimum Height Trees - 细语呢喃
leetcode Minimum Height Trees
For a 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 in
edges
. Since all edges are undirected,[0, 1]
is the same as[1, 0]
and thus will not appear together inedges
.Example 1:
Given
n = 4
,edges = [[1, 0], [1, 2], [1, 3]]
return
[1]
Example 2:
Given
n = 6
,edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
return
[3, 4]
Hint:
- How many MHTs can a graph have at most?
Note:
(1) According to the definition of tree on Wikipedia: "a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree."
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
今天新出的题 leetcode Minimum Height Trees
题意:
给定一个n个结点n-1条边的无向图(就是树啦),让你找从哪个点出发,到其他结点的最长距离最小?(返回所有答案)
思路:
一开始类似RIP来更新距离,结果TLE。证明O(n^2)的复杂度太大
只好想其他的方法。
答案一定是最长距离的中间结点位置上。
我们要的是中间结点,沿着树的外围每次把叶子结点砍掉,那么,最后剩下的不就是中间结点了么?
Read full article from leetcode Minimum Height Trees - 细语呢喃
No comments:
Post a Comment