Python solution


  • 0
    H
    class Solution(object):
        def bfs(self,n,G,start):
            parent=[i for i in xrange(n)]
            size=[0]*n
            visited={start}
            q=[start]
            while q:
                v=q.pop(0)
                for w in G[v]:
                    if w not in visited:
                        q.append(w)
                        visited.add(w)
                        parent[w]=v
                        size[w]=size[v]+1
            return parent,size
        def findMinHeightTrees(self, n, edges):
            """
            :type n: int
            :type edges: List[List[int]]
            :rtype: List[int]
            """
            G=[set() for i in xrange(n)]
            for u,v in edges:
                G[u].add(v)
                G[v].add(u)
            parent,size=self.bfs(n,G,0)
            m=max(size)
            x =size.index(m)
            parent,size=self.bfs(n,G,x)
            m=max(size)
            x =size.index(m)
            path=[x]
            y=x
            while parent[x]!=x:
                x=parent[x]
                path[:0]=[x]
            if size[y]%2:
                return[path[size[y]//2],path[size[y]//2+1]]
            return [path[size[y]//2]]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.