Minimum Height Trees

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        vector<vector<int>> adj(n);
        vector<int> deg(n, 0);
        for (auto& e : edges) {
            adj[e[0]].push_back(e[1]);
            adj[e[1]].push_back(e[0]);
            ++deg[e[0]]; ++deg[e[1]];
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) if (deg[i] == 1) q.push(i);
        int remaining = n;
        while (remaining > 2) {
            int sz = q.size();
            remaining -= sz;
            while (sz--) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) {
                    if (--deg[v] == 1) q.push(v);
                }
            }
        }
        vector<int> ans;
        while (!q.empty()) { ans.push_back(q.front()); q.pop(); }
        return ans;
    }
};

func findMinHeightTrees(n int, edges [][]int) []int {
    if n == 1 {
        return []int{0}
    }
    adj := make([][]int, n)
    deg := make([]int, n)
    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        adj[e[1]] = append(adj[e[1]], e[0])
        deg[e[0]]++
        deg[e[1]]++
    }
    q := []int{}
    for i := 0; i < n; i++ {
        if deg[i] == 1 {
            q = append(q, i)
        }
    }
    remaining := n
    for remaining > 2 {
        sz := len(q)
        remaining -= sz
        next := []int{}
        for _, u := range q {
            for _, v := range adj[u] {
                deg[v]--
                if deg[v] == 1 {
                    next = append(next, v)
                }
            }
        }
        q = next
    }
    return q
}

from typing import List
from collections import defaultdict

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        adj = defaultdict(list)
        deg = [0] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            deg[u] += 1
            deg[v] += 1
        leaves = [i for i in range(n) if deg[i] == 1]
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            nxt = []
            for u in leaves:
                for v in adj[u]:
                    deg[v] -= 1
                    if deg[v] == 1:
                        nxt.append(v)
            leaves = nxt
        return leaves

function findMinHeightTrees(n, edges) {
    if (n === 1) return [0];
    const adj = Array.from({ length: n }, () => []);
    const deg = new Array(n).fill(0);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
        deg[u]++;
        deg[v]++;
    }
    let leaves = [];
    for (let i = 0; i < n; i++) if (deg[i] === 1) leaves.push(i);
    let remaining = n;
    while (remaining > 2) {
        remaining -= leaves.length;
        const next = [];
        for (const u of leaves) {
            for (const v of adj[u]) {
                if (--deg[v] === 1) next.push(v);
            }
        }
        leaves = next;
    }
    return leaves;
}

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Arrays.asList(0);
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] deg = new int[n];
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
            deg[e[0]]++;
            deg[e[1]]++;
        }
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) if (deg[i] == 1) leaves.add(i);
        int remaining = n;
        while (remaining > 2) {
            remaining -= leaves.size();
            List<Integer> next = new ArrayList<>();
            for (int u : leaves) {
                for (int v : adj.get(u)) {
                    if (--deg[v] == 1) next.add(v);
                }
            }
            leaves = next;
        }
        return leaves;
    }
}

function findMinHeightTrees(n: number, edges: number[][]): number[] {
    if (n === 1) return [0];
    const adj: number[][] = Array.from({ length: n }, () => []);
    const deg: number[] = new Array(n).fill(0);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
        deg[u]++;
        deg[v]++;
    }
    let leaves: number[] = [];
    for (let i = 0; i < n; i++) if (deg[i] === 1) leaves.push(i);
    let remaining = n;
    while (remaining > 2) {
        remaining -= leaves.length;
        const next: number[] = [];
        for (const u of leaves) {
            for (const v of adj[u]) {
                if (--deg[v] === 1) next.push(v);
            }
        }
        leaves = next;
    }
    return leaves;
}