题目描述：
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 contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (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 in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
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.
题目大意：
对于一棵无向树，我们可以选择它的任意节点作为根。得到的结果就是有根树。在所有可能的有根树中，高度最小的称为最小高度树（MHT）。给定一个无向图，编写函数找出所有的最小高度树，并返回其根标号的列表。
格式：
图包含n个节点，标号为0到n-1。给定数字n以及一列无向边（每条边用一对标号表示）
你可以假设边没有重复。由于所有边都是无方向的，因此[0, 1]与[1, 0]是等价的。因而它们不会同时出现在边集合中。
测试用例如题目描述。
提示：
最多可能存在多少个MHT？
注意：
(1) 根据维基百科的定义：“一棵树是一个满足这样性质的无向图：任意两个节点之间只存在一条路径相连。或者说，任意不包含简单环路的连通图叫做树”。
(2) 有根树的高度为从根部到叶子节点的路径中最长的那一条的边数。
解题思路：
参考LeetCode Discuss，链接地址：https://leetcode.com/discuss/71656/c-solution-o-n-time-o-n-space
基本思路是“逐层删去叶子节点，直到剩下根节点为止”
有点类似于拓扑排序
最终剩下的节点个数可能为1或者2
时间复杂度：O(n)，其中n为顶点的个数。
Python代码：
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
children = collections.defaultdict(set)
for s, t in edges:
children[s].add(t)
children[t].add(s)
vertices = set(children.keys())
while len(vertices) > 2:
leaves = [x for x in children if len(children[x]) == 1]
for x in leaves:
for y in children[x]:
children[y].remove(x)
del children[x]
vertices.remove(x)
return list(vertices) if n != 1 else [0]
下面的写法速度更快，参考：https://leetcode.com/discuss/71763/share-some-thoughts
Python代码：
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
children = [set() for x in range(n)]
for s, t in edges:
children[s].add(t)
children[t].add(s)
leaves = [x for x in range(n) if len(children[x]) <= 1]
while n > 2:
n -= len(leaves)
newLeaves = []
for x in leaves:
for y in children[x]:
children[y].remove(x)
if len(children[y]) == 1:
newLeaves.append(y)
leaves = newLeaves
return leaves
另附朴素解法，毫无悬念的Time Limit Exceeded：
Python代码：
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if n == 1: return [0]
children = collections.defaultdict(set)
for s, t in edges:
children[s].add(t)
children[t].add(s)
l = []
for v in children:
l += (v, self.findHeight(v, children)),
minHeight = min(x[1] for x in l) if l else 0
return [x[0] for x in l if x[1] == minHeight]
def findHeight(self, root, children):
height = 0
for c in children[root]:
children[c].remove(root)
height = max(height, self.findHeight(c, children))
children[c].add(root)
return height + 1
本文链接：http://bookshadow.com/weblog/2015/11/26/leetcode-minimum-height-trees/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
good job