LeetCode - 310. Minimum Height Trees [Python]

https://leetcode.com/problems/minimum-height-trees/

Minimum Height Trees - LeetCode

---

풀이 과정

트리간의 연결 관계가 주어지는데, 어떤 노드를 root로 삼아야 가장 높이가 낮은 트리를 구성할 수 있는지 묻는 문제이다.

 

남은 노드가 2개 이하가 될 때 까지, 리프 노드를 제거해가면서 문제를 해결하였다.

---

소스 코드

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]
        
        graph = collections.defaultdict(list)
        for s, d in edges:
            graph[s].append(d)
            graph[d].append(s)
            
        leaves = []
        
        for s in graph:
            if len(graph[s]) == 1:
                leaves.append(s)
        
        while n > 2:
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neigh = graph[leaf].pop()
                graph[neigh].remove(leaf)
                if len(graph[neigh]) == 1:
                    new_leaves.append(neigh)
            leaves = new_leaves
        
        return leaves