2018年10月14日
#310. Minimum Height Trees
问题描述：
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
样例：
Example 1 :
Input:
n = 4
,
edges = [[1, 0], [1, 2], [1, 3]]0|1/ \2 3 Output:
[1]Example 2 :
Input:
n = 6
,
edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]0 1 2\ | /3|4|5 Output:
[3, 4]Note:
- According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactlyone path. In other words, any connected graph without simple cycles is a tree.”
- The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
问题分析：
本题难度为Medium！已给出的函数定义为：
class Solution(object):def findMinHeightTrees(self, n, edges):""":type n: int:type edges: List[List[int]]:rtype: List[int]"""其中，n为结点数，edges为边的二维数组。
第一次看到这道题，首先想到的是遍历每个结点，以每个结点作为树的根结点，计算树的高度，然后比较找出最小的树的高度。
代码实现：
#coding=utf-8
class Solution:def findMinHeightTrees(self, n, edges):""":type n: int:type edges: List[List[int]]:rtype: List[int]"""def isLeaf(graph, vertex):if len(graph[vertex])==1:return Truereturn False# length记录每条路径长度，stack为dfs栈，visited为标记列表def dfs(lengths, stack, visited, graph, deepdegree, minLen): vertex=stack.pop()if deepdegree>minLen:lengths.append(n)return if isLeaf(graph,vertex) and deepdegree!=0: #判断叶结点lengths.append(deepdegree)else:deepdegree+=1for v in graph[vertex]:if v not in visited:cp_v=visited.copy();cp_v.append(v)cp_s=stack.copy();cp_s.append(v)dfs(lengths,cp_s,cp_v,graph,deepdegree,minLen)if n==1: return [0]# 建图graph=[[] for i in range(n)]for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])res=[] #存储结果结点minLen=n #初始化最小树高度for v in range(n):lengths=[];stack=[];visited=[]# 放入root结点stack.append(v)visited.append(v)deepdegree=0dfs(lengths,stack,visited,graph,deepdegree,minLen)if max(lengths)<minLen:res=[v]minLen=max(lengths)elif max(lengths)==minLen:res.append(v)return res但是这种算法的时间复杂度比较大，生成graph图的时间复杂度为O(E)，由于此题的图的特殊性，所以E=V-1；遍历所有结点的时间复杂度为O(V)，遍历的每一次DFS算法时间复杂度为O(V)，所以总的时间复杂度为O(V*V)。当n比较大时，计算时间太慢，无法通过leetcode的全部检测。即使在DFS中用了一个小技巧deepdegree<minLen来降低计算时间，但还是太慢了。
通过查阅资料发现有一种剥洋葱法，可以把时间复杂度降到O(2V)。
算法如下：
1.向前面所述的第一种算法的代码实现一样，遍历所有边，生成新的图的邻接表表示法，graph为一个二维数组，graph[i]为一维数组，存储的是结点i的邻接结点。建一个一维的结点数组存储所有的结点。
2.遍历所有结点，用一个数组存储叶结点，即graph[i]长度为1的 i。
3.遍历叶结点数组，在graph中删除叶结点的边，并在结点数组中删除该叶结点，然后将该叶结点的邻接结点放进一个新数组；遍历结束后清空叶结点数组。
4.遍历这个邻接结点组成的新数组，将如果邻接结点也变成了叶结点，则放入叶结点数组中。
5.循环步骤3、4直到结点数组剩下1或2个结点。剩下的结点就是最小高度树的根结点。
代码实现：
#coding=utf-8
class Solution:def findMinHeightTrees(self, n, edges):""":type n: int:type edges: List[List[int]]:rtype: List[int]"""# 建图graph=[[] for i in range(n)]for edge in edges:graph[edge[0]].append(edge[1])graph[edge[1]].append(edge[0])vertex_list=[i for i in range(n)] # 存储保留的vertexleaf_list=[] # 存储leaf vertex# 遍历所有vertex，存储leaf vertexfor v in range(n):if len(graph[v])==1:leaf_list.append(v)while len(vertex_list)>2: # 剥去叶结点，更换新结点temp_list=[]for v in leaf_list:adj_v=graph[v].pop()graph[adj_v].remove(v)vertex_list.remove(v)if adj_v not in temp_list: temp_list.append(adj_v) # 添加邻接结点到新列表中待统计leaf vertexleaf_list.clear() # 清空列表for v in temp_list: # 统计leaf vertexif len(graph[v])==1:leaf_list.append(v)return vertex_list该算法可以通过leetcode的全部检测！