[LeetCode] 310. Minimum Height Trees

😎풀이

1. edges 배열에 담긴 정보를 통해 이웃한 노드끼리 간선을 연결한다.
2. 리프 노드를 탐색한다. 이 때 리프 노드란 연결된 간선이 하나뿐인 노드로 가장자리에 존재하는 노드를 의미한다. (해당 노드를 통해 중앙 노드를 순차적으로 탐색)
3. 가장자리부터 순차적으로 제거하여 노드가 2개 이하로 존재할 경우 잔여 노드는 중앙 노드를 의미한다.
   3-1. 탐색할 노드의 수를 잔여 노드 수에서 뺀다.
   3-2. 탐색 노드를 순회하며 이웃한 노드에서 현재 탐색중인 노드를 제거해가며 이웃한 노드가 하나 남았다면 해당 노드를 탐색할 목록에 추가한다.
4. 중앙 노드를 최종 반환한다.

function findMinHeightTrees(n: number, edges: number[][]): number[] {
    if(n === 1) return [0]

    const adjList = new Map<number, Set<number>>()
    // 간선 연결
    for(const [from, to] of edges) {
        if(!adjList.has(from)) adjList.set(from, new Set())
        if(!adjList.has(to)) adjList.set(to, new Set())
        adjList.get(from).add(to)
        adjList.get(to).add(from)
    }

    // 리프 노드 탐색
    let leaves = []
    for(const [node, neighbor] of adjList) {
        if(neighbor.size === 1) leaves.push(node)
    }

    // 간선 제거를 통한 중심 노드 탐색
    let remain = n;
    while(remain > 2) {
        remain -= leaves.length
        const nextLeaves = []
        for(const leaf of leaves) {
            const neighbor = adjList.get(leaf).values().next().value
            adjList.get(neighbor).delete(leaf)
            if(adjList.get(neighbor).size === 1) nextLeaves.push(neighbor)
        }
        leaves = nextLeaves
    }

    return leaves
};