Leetcode 310. Minimum Height Trees(python)

题目

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.

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.

解法：拓扑排序+BFS

首先简单分析一下这个题目。题目给定的是一个无向图，要我们求得是以某个节点构成的树（不一定是二叉树）的最低高度。那么其实换句话说想让我们找的是给定无向图最中心的点。因为最中心的点和图中任意一个点的最远距离最小，以这个中心点为root构成的树的节点也就会最小。可以利用拓扑排序的思想
这个题目值得注意的一点是，最后形成的这个root list一定只会是1或2
解题流程：

• 创建一个字典，保存所有节点的相邻节点组成的set
• 从字典中寻找相邻节点有且只有一个的节点，类似于拓扑排序中寻找入度为0的点，将所有符合要求的这样的点放入队列中，作为初始队列进入循环
• 遍历队列中所有的节点u，从这个节点的相邻节点v的相邻节点集合nodes[v]中删除u这个节点
• 如果这个时候nodes[v]只有一个元素，也就是说v现在只有一个相邻节点的时候，说明这个节点是叶节点，将v放入队列中
• 循环终止条件为队列中的节点个数为1或者2，这个时候队列中的元素即为所求答案

class Solution:def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:if n == 1: return [0]nodes = collections.defaultdict(set)for u,v in edges:nodes[u].add(v)nodes[v].add(u)q = collections.deque()for u,vs in nodes.items():if len(vs) == 1: q.append(u)while n>2:_len = len(q)n -= _lenfor _ in range(_len):u = q.popleft()for v in nodes[u]:nodes[v].remove(u)if len(nodes[v]) == 1:q.append(v)return list(q)

时间复杂度：O(E), E为图中边的条数，因为最终每个边会被访问两次
空间复杂度：O(E+N), N为节点数，字典消耗的空间加队列消耗的空间

参考链接