❗️[LEET CODE] 310. Minimum Height Trees

# Problem

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h))  are called minimum height trees (MHTs). Return a list of all MHTs' root labels. You can return the answer in any order. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf. Constraints: 1 <= n <= 2 * 104 edges.length == n - 1 0 <= ai, bi < n ai != bi All the pairs (ai, bi) are distinct. The given input is guaranteed to be a tree and there will be no repeated edges.

 

# My Answer

import collections
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        ed = [0 for _ in range(n)]
        rt = [i for i in range(n)]
        
        if len(ed)<=2:
            return rt
            
        # d에 연결된 간선 정보 저장
        d = collections.defaultdict(list)
        for i in edges:
            ed[i[0]]+=1
            ed[i[1]]+=1
            d[i[0]].append(i[1])
            d[i[1]].append(i[0])
		

        while len(set(ed))>2 or 0 not in ed:
            temp=[]
            for i,e in enumerate(ed):
                if e==1:
                    temp.append(i)
            for i in temp:
                rt.remove(i)
                ed[i]-=1
                d[d[i][0]].remove(i)
                ed[d[i][0]]-=1
        return rt

rt에는 처음에 모든 노드를 넣어두고 연결된 간선이 1인 것부터 순서대로 삭제한다.

ed에는 인덱스를 노드번호라고 할때 연결된 간선의 수를 저장한다.

d에는 딕셔너리형으로 연결된 간선 정보를 저장한다.

 

ed에 0,1 외에 더 많이 연결된 노드가 있거나,

[1,3,1,1] 과 같이 하나의 노드에 모든 다른 노드들이 연결된 경우 (set(ed)의 원소는 2개지만 0이 없음)

연결된 간선이 1인 노드부터 (리프노드) 삭제한다.

 

ed의 값이 모두 0이 되거나 0과 1만 남을 경우 rt에 저장되어 있는 값들은 모두 루트 노드가 될 수 있다. 

 

# Solution 1 - 단계별 리프 노드 제거

import collections

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


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:
            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

1. leaves에 리프노드를 추가한다 ( 연결된 간선이 1인 노드 )

2. leaves의 노드 leaf에 연결된 노드들의 간선 리스트에서 leaf 제거

3. leaf삭제 후 연결된 간선이 1이 된 노드들은 새로운 리스트 new_leaves에 추가

4. new_leaves에 대해 2,3번 반복 ( 루트 노드만 남을 때까지 )

5. 마지막 leaves 리스트가 루트노드가 될 수 있는 노드 

마지막에 n이 1이면 루트 노드 1개, n이 2이면 서로 연결된 간선 하나 존재로 루트 노드 2개가 된다. ( n>2이면 반복 )

루트노드는 3개 이상이 될 수 없다 ( 무조건 더 적게 연결된 노드 하나 존재 )