难度: Medium
原题连接
内容描述
For an 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 exactly one 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.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
首先我们要找到一棵树，使得它的高度最短
并且这是一个联通的图，因此我们试图找到一个点，从它往外延伸出去的距离最短，那么这样一个点势必就是整个图的中心点。
换句话说，如果这个图当中有一条最长路径的话，那么这个最长路径的中点就是我们要找的那个点， 当最长路径长度为奇数时（因为这个时候最长路径上的点的个数就是奇数），这样的中点有两个
那么问题来了，怎么找到最长路径呢
有这样一个办法：
- Pick arbitrary starting node
- Do a BFS/DFS search (it does not matter as trees have unique paths), keeping track of the farthest node (any will make the trick, as there could be several with same distance from starting node)
- Repeat step 1. but starting from the farthest node found. The path from this new starting point ands its new farthest node will be the diameter of the tree.
- There is a theorem saying that center lies at the middle of the diameter, seen as a path. If such path has odd length, there are two centers.
用第二个input作为例子吧，start是0，farthest1是5，farthest2是2，然后max_dist是3，所以退后一格找到3， 由于max_dist是奇数，所以一共有两个中点，再向后退一格找到4，最后结果就是[3, 4]
但是如果我们从farthest1继续找，我们回到了点0呢？那就更简单了，还是退一格找到3，再退一格找到4。 也就是说不管从farthest1能不能找到比0能远的点或者一样远的点，我们都可以通过从farthest2往后退的方式得到结果
参考
beats 35.44%
class Solution(object):
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if not edges:
return [0] * n
tree = collections.defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
start = list(tree.keys())[0]
_, farthest1, _ = self.search_farthest(tree, start)
max_dist, farthest2, parent = self.search_farthest(tree, farthest1)
node = farthest2
for _ in range(max_dist//2):
node = parent[node]
roots = [node]
if max_dist % 2 == 1:
roots.append(parent[node])
return roots
def search_farthest(self, tree, start):
stack = [(start, 0)]
parent = dict()
visited = set()
max_dist = 0
while stack:
node, dist = stack.pop()
if node in visited:
continue
visited.add(node)
if dist > max_dist:
max_dist = dist
farthest = node
for child in tree[node]:
if child not in parent:
parent[child] = node
stack.append((child, dist+1))
return max_dist, farthest, parent思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******
第二个思路就是我们已经把这个图看成一棵树了，那么树肯定会有叶子节点，我们一层一层删除掉叶子节点，然后去除他们与上一层的关系， 然后上一层又变成叶子节点了，重复这个步骤，直到节点只剩下一个或者两个，因为按照思路一里面的论证，最后的中点只会有一个或者两个
beats 88.35%
class Solution:
def findMinHeightTrees(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: List[int]
"""
if n <= 1:
return [0]
graph = collections.defaultdict(list)
for v1, v2 in edges:
graph[v1].append(v2)
graph[v2].append(v1)
leaves = [i for i in range(n) if len(graph[i]) == 1]
while n > 2:
n -= len(leaves)
new_leaves = []
for leaf in leaves:
node = graph[leaf].pop()
graph[node].remove(leaf)
if len(graph[node]) == 1:
new_leaves.append(node)
leaves = new_leaves
return leaves