# Leetcode 310. Minmum height trees

## 暴力深度優先搜索 (超時)

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # O(n**2) solution 
        # timeout
        graph = [[] for _ in range(n)]
        visit = [False for _ in range(n)]
        minHeight = 2 * (10 ** 4)
        output = {}

        for ai,bi in edges:
            graph[bi].append(ai)
            graph[ai].append(bi)
        
        def dfs(node: int, height: int, visit: List[bool]):
            visit[node] = True
            height += 1
            maxHeight = height
            for neighbor in graph[node]:
                if not visit[neighbor]:
                    maxHeight = max(maxHeight,dfs(neighbor, height, visit))
            visit[node] = False
            return maxHeight
        
        for node in range(n):
            height = dfs(node, 0, visit)
            if height in output:
                output[height].append(node)
            else:
                output[height] = [node]
            minHeight = min(minHeight,height)
        
        return output[minHeight]