Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
966 B
10
Indexable
Never
    def find_min_height_trees(self, n: int, edges: List[List[int]]) -> List[int]:
        # Wirte your code here

        graph = collections.defaultdict(list)
        for n1, n2 in edges:
            graph[n1].append(n2)
            graph[n2].append(n1)
        
        path1 = []
        self.dfs(graph, None, 0, 0, [0], 0, path1)
        end1 = path1[-1]
        path2 = []
        self.dfs(graph, None, end1, 0, [end1], 0, path2)

        if len(path2) % 2 == 0:
            return [path2[len(path2)// 2 - 1],path2[len(path2)// 2]]
        return [path2[len(path2)// 2]]
    
    def dfs(self, graph, prev, curr, dis, path, max_dis, result):
        if len(graph[curr]) == 1 and prev is not None:
            if dis > max_dis:
                max_dis, result = dis, path[:]
            return

        for next in graph[curr]:
            if next == prev:
                continue
            self.dfs(graph, curr, next, dis + 1, path + [next], max_dis, result)