310. 最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含n个节点的树，标记为0到n-1。给定数字n和一个有n-1条无向边的edges列表（每一个边都是一对标签），其中edges[i] = [ai, bi]表示树中节点ai和bi之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点x作为根节点时，设结果树的高度为h。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

示例 3：

输入：n = 1, edges = []
输出：[0]

示例 4：

输入：n = 2, edges = [[0,1]]
输出：[0,1]

提示：

• 1 <= n <= 2*10^4
• edges.length == n - 1
• 0 <= ai, bi < n
• ai != bi
• 所有(ai, bi)互不相同
• 给定的输入保证是一棵树，并且不会有重复的边

1.遍历超时
Python解答：

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        adic = {}
        for item in edges:
            if item[0] not in adic.keys():
                adic[item[0]] = [item[1]]
            else:
                adic[item[0]].append(item[1])
            if item[1] not in adic.keys():
                adic[item[1]] = [item[0]]
            else:
                adic[item[1]].append(item[0])
        def compute(k):
            high = 0
            flag = [True for i in range(n)]
            nodes = [k]
            if adic:
                while nodes:
                    new = []
                    for node in nodes:
                        flag[node] = False
                        for item in adic[node]:
                            if flag[item]:
                                new.append(item)
                    high += 1
                    nodes = new
            return high

        value = [0 for i in range(n)]
        for i in range(n):
            value[i] = compute(i)
        lowest = min(value)
        return [i for i in range(n) if value[i]==lowest]

2.拓扑排序

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        adic = {}
        degree = [0 for i in range(n)]
        flag = [True for i in range(n)]
        for item in edges:
            degree[item[0]] += 1
            degree[item[1]] += 1
            if item[0] not in adic.keys():
                adic[item[0]] = [item[1]]
            else:
                adic[item[0]].append(item[1])
            if item[1] not in adic.keys():
                adic[item[1]] = [item[0]]
            else:
                adic[item[1]].append(item[0])
        if n == 1:
            return [0]
        elif n == 2:
            return [0,1]
        nodes = [i for i in range(n) if degree[i] == 1]
        while len(nodes) > 0:
            for i in nodes:
                temp = adic[i]
                degree[i] -= 1
                flag[i] = False
                for j in temp:
                    degree[j] -= 1
            nodes = [k for k in range(n) if degree[k] == 1]
            remain = [i for i in range(n) if flag[i]]
            if len(remain) <= 2:
                return remain