class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
#a graph has maxmimum 2 minimum height tree
#peel away the leaves one layer at a time until there are two or fewer nodes
if n==1: return [0]
adj=[set() for _ in range(n)]
for i,j in edges:
adj[i].add(j)
adj[j].add(i)
leaves=[i for i in xrange(n) if len(adj[i])==1]
while n>2:
n-=len(leaves)
new_leaves=[]
for leave in leaves:
j=adj[leave].pop()
adj[j].remove(leave)
if len(adj[j])==1:new_leaves.append(j)
leaves=new_leaves
return leaves
310. Minimum Height Trees
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- For a undirected graph with tree characteristics, we can ...
- For a undirected graph with tree characteristics, we can ...
- For a undirected graph with tree characteristics, we can ...
- p.p1For a undirected graph with tree characteristics, we ...
- 问题描述 For a undirected graph with tree characteristics, we...
