Leetcode 310. Minimum Height Trees(python+cpp)

题目

解析：拓扑排序+BFS

这道题目很巧妙，需要灵活运动对于图的理解。题目原本的说法是要找到某个节点，使得以其为根节点所组成的多叉树的高度最小，那么换个方式来理解，就是要找到图中最中心的节点，以最中心的节点为根节点组成的图一定就是高度最矮的。
那么如何找最中心的节点呢？这边其实思想跟934 shortest bridge的思想有点像，那倒题目是通过以一个岛为中心，利用BFS一层层向外扩散来解决的。而这边则可以反过来，从外侧一层层向里进行收缩来完成，而由于这边是个无向图，所以我们需要利用到拓扑排序的思想，具体如下：

• 首先利用字典构建节点间的邻接关系
• 将所有初始的时候入度为1的节点作为BFS的起点，这些入度为1的节点说明位于图的最外圈
• 进行BFS，每次需要移除当前图中所有入度为1的节点，并将新生成的入度为1的节点放入队列待后续操作
• 最关键的一步在于结束条件的判断，由于题中说明提供的图是具有树的特性的，那么一定不会存在环，所以当队列中只剩下1个或者2个结点的时候，队列中的节点便一定是中心节点

python代码如下：

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

C++代码如下：
用C++写需要注意以下几个点：

• 需要手动构建一个map，类似于python里的collection.defaultdict(list)。
• 关于删除vector里面特定元素的表达方式：q.erase(find(q.begin(),q.end(),curr)); 我好像没有找到其他更简洁的方式，所以导致C++的解法有点慢
• 关于我们一次移除所有入度为1的节点时，是通过for循环来实现的，但是与python不同的是，C++中vector的长度可以动态的变化，所以需要将当前q的长度预存成一个变量

class Solution {
    
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    if (n==1) return {
    0};map<int,set<int>> graph;for (auto edge:edges){
    graph[edge[0]].insert(edge[1]);graph[edge[1]].insert(edge[0]);}vector<int> q;for (auto iter:graph){
    if (iter.second.size()==1) q.push_back(iter.first);}while (n>2){
    n = n - q.size();// 这边要注意int len = q.size();for (int i=0;i<len;++i){
    int curr = q.front();q.erase(find(q.begin(),q.end(),curr));for (auto neigh:graph[curr]){
    graph[neigh].erase(curr);if (graph[neigh].size()==1) q.push_back(neigh);}}}return q;}
};

参考链接