310. Minimum Height Trees

Minimum Height Trees - LeetCode

1. Brute Force DFS (시간 초과)

from typing import *
from collections import defaultdict


class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(set)
        for edge in edges:
            src, dsc = edge
            graph[src].add(dsc)
            graph[dsc].add(src)

        def sol(cur, graph, visited):
            visited[cur] = 1
            res, flag = 0, 0
            for adj in graph[cur]:
                if not visited[adj]:
                    flag = 1
                    res = max(sol(adj, graph, visited), res)
            if not flag:
                return 1
            return res + 1

        min_height, answer = float("inf"), [0]
        for node in graph:
            temp = sol(node, graph, [0] * n)
            if temp < min_height:
                min_height = temp
                answer = [node]
            elif temp == min_height:
                answer.append(node)
        return answer

 

2. Topological Sort (위상 정렬) 응용

from typing import *
from collections import defaultdict, deque


class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if len(edges) == 1:
            return edges[0]

        graph = defaultdict(set)
        indegree = [0] * n
        for edge in edges:
            src, dsc = edge
            graph[src].add(dsc)
            graph[dsc].add(src)
            indegree[src] += 1
            indegree[dsc] += 1
        q = deque([])
        for node in graph:
            if indegree[node] == 1:
                q.append(node)
        left_node_num = n
        answer = [0]
        while left_node_num > 2:
            deleted_node, candi_node = [], []
            while q:
                cur = q.popleft()
                deleted_node.append(cur)
                for adj in graph[cur]:
                    graph[adj].remove(cur)
                    indegree[adj] -= 1
                    if indegree[adj] == 1:
                        candi_node.append(adj)
            left_node_num -= len(deleted_node)
            q = deque(candi_node)
            answer = candi_node
        return answer

3. Tree DP 

추후 기술