최소 높이 트리

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

Minimum Height Trees - LeetCode

 

 최소 높이를 구성하려면 가장 가운데에 있는 값이 루트여야 한다. 이 말은 리프 노드를 하나씩 제거해 나가면서 남아 있는 값을 찾으면 이 값이 가장 가운데에 있는 값이 될것이고, 이 값을 루트로 했을 때 최소 높이를 구성할 수 있다는 뜻이기도 하다.

 

 이 문제에서 그래프는 무방향이므로, 트리의 부모와 자식은 양쪽 노드 모두 번갈아 가능하다.

 

 리프 노드를 찾아서 leaves에 추가한다. 리프 노드는 그래프에서 해당 키의 값이 1개뿐인 것을 말한다.

 이중에서 값이 1개 뿐인 [1,2,10,7,9]가 첫 번째 리프 노드로 leaves 리스트 변수에 담기게 된다.

 

 n은 전체 노드의 개수이므로 여기서 leaves, 즉 리프 노드의 개수만큼 계속 빼나가면서 최종 2개 이하가 남을 때까지 반복한다.

 마지막에 남은 값이 홀수 개일 때는 루트가 최종 1개가 되지만, 짝수 개일 때는 2개가 될 수 있다.

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n<=1:
            return [0]
        
        graph=collections.defaultdict(list)
        for i,j in edges:
            graph[i].append(j)
            graph[j].append(i)
            
        leaves=[]
        for i in range(n+1):
            if len(graph[i]) == 1:
                leaves.append(i)
                    
        
        
        while n>2:
            #print(leaves)
            n -=len(leaves)
            new_leaves=[]
            for leaf in leaves:
                # 서로 연결관계를 삭제하는 과정
                neighbor=graph[leaf].pop()
                graph[neighbor].remove(leaf)
                
                if len(graph[neighbor]) ==1:
                    new_leaves.append(neighbor)
                    
            leaves=new_leaves
            
        return leaves