## 题目描述：

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.

## 题目大意：

(1) 根据维基百科的定义：“一棵树是一个满足这样性质的无向图：任意两个节点之间只存在一条路径相连。或者说，任意不包含简单环路的连通图叫做树”。

(2) 有根树的高度为从根部到叶子节点的路径中最长的那一条的边数。

## 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]
``````

## 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
``````

## 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
``````

Pingbacks已关闭。

1. gracesrm 发布于 2015年11月28日 12:52 #

good job