Compact Python solution using two BFS

  • 3
    class Solution(object):
        def findMinHeightTrees(self, n, edges):
            graph = [[] for i in range(n)]
            for v1, v2 in edges:
            p1 = self.FindLongestPath(graph, 0)
            p2 = self.FindLongestPath(graph, p1[-1])
            if len(p2) % 2: return [p2[len(p2)/2]]
            else:           return [p2[len(p2)/2 - 1], p2[len(p2)/2]]
        def FindLongestPath(self, graph, root):
            queue = collections.deque([[root]])
            traversed = set([root])
            while queue:
                path = queue.pop()
                for v in graph[path[-1]]:
                    if v not in traversed:
                        queue.appendleft(path + [v])
            return path

  • 0

    Could you explain it? It is not so obvious.

  • 0
    queue.appendleft(path + [v])

    This way of keeping track of paths can cost you O(n^2) space. If you have an O(N) number of branches later on you'll be keeping track of O(N) paths with each of them taking up O(N) space. Consider a tree that keeps breaking out into multiple branches.

Log in to reply

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