Python O(N) time O(N) space


  • 0

    First BFS from an arbitrary vertex to find the starting/ending point of the longest path. Then do another BFS from that source vertex to find the longest path. We just need to keep track of parents as a tree cannot have a cycle and, therefore, each vertex can only have a single parent/source when we're doing a BFS traversal in one direction. For this same reason, we can argue that keeping track of parents only will be limited to using O(N) space. Could be further optimized by not keeping track of parents in the first BFS, but that would require to rewrite or put in an extra comparison in the BFS method, so decided to leave it out.

        def findMinHeightTrees(self, n, edges):
    
            def makeGraph(E):
                graph = collections.defaultdict(set)
                for e in E:
                    graph[e[0]].add(e[1]) 
                    graph[e[1]].add(e[0])
                return graph
                
            def BFS(start, G):
                parents, visited = {}, set()
                queue = collections.deque([(start, 0, None)])
                V, farthest = None, 0
                while queue:
                    v, dist, p = queue.popleft()
                    if dist > farthest: farthest, V = dist, v
                    visited.add(v)
                    parents[v] = p
                    for vtx in G[v]:
                        if vtx not in visited: queue.append((vtx, dist+1, v))
                return V, farthest, parents
                
            if not edges: return [0] if n == 1 else []
            G = makeGraph(edges)
            end, farthest, parents = BFS(BFS(0, G)[0], G)
            vCount = farthest + 1
            target, root, prev = vCount // 2, None, None
            while target > -1:
                root, prev = end, root
                end = parents[end]
                target -= 1
            return [root] if vCount % 2 != 0 else [root, prev]
    

Log in to reply
 

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