思路
第一次，采用逐个节点进行dfs，然后取最小的深度，超时了。class Solution(object): def findMinHeightTrees(self, n, edges): res = [0 for j in range(0, n)] for k in range(0, n): visit = [False for j in range(0, n)] def dfs(res,edges, n, i, level, visit): if(level>res[k]): res[k] = level visit[i] = True for j in range(0, len(edges)): if (edges[j][0] == i and not visit[edges[j][1]]): dfs(res,edges, n, edges[j][1], level + 1, visit) if (edges[j][1] == i and not visit[edges[j][0]]): dfs(res,edges, n, edges[j][0], level + 1, visit) bfs(res,edges, n, k, 0, visit) minheightIndex = [0] for i in range(1, len(res)): if (res[i] < res[minheightIndex[0]]): minheightIndex = [i] elif (res[i] == res[minheightIndex[0]]): minheightIndex.append(i) return minheightIndex第二次，采用另一种想法，就是计算每个节点的度，然后找出度为1的节点（叶子节点），然后删除，并把叶子节点的相邻节点的度进行更新。最后发现这种方法也过了58／68个样例，还是超时。class Solution(object): def findMinHeightTrees(self, n, edges): #initial degreeZero = [i for i in range(0,n)] while (True): degree = [0 for j in range(0, n)] for i in range(len(edges)): if(edges[i][0]!= -1): degree[edges[i][0]] += 1 degree[edges[i][1]] += 1 degreeOne = [] zero = 0 # find degree one if(len(degreeZero) == 2 or not len(degreeZero)): return degreeZero for i in range(len(degree)): if (degree[i] == 1): degreeOne.append(i) # update degree for i in range(len(degreeOne)): for j in range(len(edges)): if (edges[j][0] == degreeOne[i] or edges[j][1] == degreeOne[i]): degreeZero.remove(degreeOne[i]) edges[j][0] = -1 edges[j][1] = -1第三次，后来实在没办法，之后上网参考大神的想法，不断删除叶子节点，逐渐逼近根节点的方法，在删除叶子节点的同时，会有一些新的节点成为叶子节点，于是继续循环删除，直至不能删除为止，那么剩下的节点就是高度最小的根。和我的第二种思路有一点点相似。但是，我第二种思路，没有用数组把每个点的相邻边进行存储，而是每次都进行edges的遍历去重置每个节点的度。AC代码
import collections;class Solution(object): def findMinHeightTrees(self, n, edges): #initial #e:set of link node if n == 1: return [0] e = collections.defaultdict(list) for x,y in edges: e[x].append(y) e[y].append(x) res = list(e.keys()) while(len(res)>2): leaves = [x for x in e if len(e[x]) == 1] for j in range (0,len(leaves)): for y in range (0,len(e[leaves[j]])): if(y == j): e[y].remove(leaves[j]) del e[leaves[j]] res.remove(leaves[j]) return res
