本文主要是介绍310. 最小高度树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
310. 最小高度树
题目链接：310. 最小高度树
代码如下：
//BFS/拓扑排序二分树
//参考：https://leetcode.cn/problems/minimum-height-trees/solutions/524029/c-xun-xu-jian-jin-de-si-lu-bfsdfstuo-bu-hmk2y
class Solution {
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if(n==1) return {0};//创建无向邻接图vector<vector<int>> adjList(n);vector<int> degree(n,0);for(int i=0;i<edges.size();i++){adjList[edges[i][0]].emplace_back(edges[i][1]);adjList[edges[i][1]].emplace_back(edges[i][0]);++degree[edges[i][0]];++degree[edges[i][1]];}queue<int> que;for(int i=0;i<n;i++){if(degree[i]==1)que.emplace(i);}while(!que.empty()){int size=que.size();if(size==n) break;//终止条件n-=size;while(size--){int cur=que.front();que.pop();//访问邻接点，找出下一个正确的adjint adj;for(int i=0;i<adjList[cur].size();i++){adj=adjList[cur][i];if(degree[adj]>1) break;}--degree[adj];if(degree[adj]==1)que.emplace(adj);}}vector<int> res;while(!que.empty()){res.emplace_back(que.front());que.pop();}return res;}
};
这篇关于310. 最小高度树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
