310.minimum-height-trees.md

310. Minimum Height Trees

fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
    if (n == 1) return listOf(0)

    val degrees = IntArray(n)
    val graph = Array(n) { mutableListOf<Int>() }
    for ((a, b) in edges) {
        degrees[a]++
        degrees[b]++
        graph[a].add(b)
        graph[b].add(a)
    }

    val queue = ArrayDeque<Int>()
    for (i in degrees.indices) {
        if (degrees[i] == 1) {
            queue.addLast(i)
        }
    }
    var remaining = n
    while (remaining > 2) {
        val size = queue.size
        repeat(size) {
            val node = queue.removeFirst()
            remaining--
            graph[node].forEach { adj ->
                degrees[adj]--
                if (degrees[adj] == 1) {
                    queue.addLast(adj)
                }
            }
        }
    }
    return queue
}