[LeetCode] Minimum Height Tree

leetcode

Topological Sort to find root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def findMinHeightTrees(self, n, edges):
    # Wirte your code here
    if n == 1: return [0]

    graph = [[] for x in range(n)]
    degree = [0] * n

    for e in edges:
        graph[e[0]].append(e[1])
        graph[e[1]].append(e[0])
        degree[e[0]] += 1
        degree[e[1]] += 1

    # from leaf node
    leaves = [i for i in range(n) if degree[i] == 1]

    nodes = n
    while nodes > 2:
        newleaves = []
        for i in leaves:
            degree[i] = 0
            nodes -= 1
            for j in graph[i]:
                degree[j] -= 1
                if degree[j] == 1:
                    newleaves.append(j)
        leaves = newleaves
    return leaves