Compact Python solution using two BFS


  • 3
    K
    class Solution(object):
        def findMinHeightTrees(self, n, edges):
            graph = [[] for i in range(n)]
            for v1, v2 in edges:
                graph[v1].append(v2)
                graph[v2].append(v1)
            
            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])
                        traversed.add(v)
            return path

  • 0
    W

    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.