310. Minimum Height Trees

link

Cut the leaf node until the node left <= 2

Leaf node = indeg == 1

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        
        if n == 1:
            return [0]

        if n == 2:
            return [0,1]

        M = defaultdict(list)

        indeg = [0] * n


        for [v1, v2] in edges:
            M[v1].append(v2)
            M[v2].append(v1)
            indeg[v1] += 1
            indeg[v2] += 1

    
        dq = deque([i for i in range(n) if indeg[i] == 1])


        s = set()

        while dq:

            lens = len(dq)

            for _ in range(lens):
                idx = dq.popleft()

                indeg[idx] -= 1

                s.add(idx)

                for vv in M[idx]:
                    indeg[vv] -= 1
                    if indeg[vv] == 1:
                        dq.append(vv)

        
            if n - len(s) <= 2:
                break

        return dq