BFS 求解 最小高度树 【妙用】

310. 最小高度树

链接 ：题目链接

• 思路
  • 常规解法是树形dp，两个dfs解决，这里不再赘述
  • 新颖解法bfs，而且实现更加简单，大体思路就是每次都从叶子节点一步步往中心爬，最后一批留在队列中的节点就为本题意的答案,具体实现思路就是每次更新叶子节点，也就是把之前的叶子节点扔掉，然后和它相连的节点度数减一产生新的叶子节点。

代码

class Solution {
public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {if(n == 1) return {0};vector<int> out(n+10);// 统计每个点的出度vector<vector<int>> e(n+10);for(auto i : edges){int a = i[0];int b = i[1];out[a] ++, out[b] ++;e[b].push_back(a);// 建立邻接表e[a].push_back(b);}vector<int> res;queue<int> q;for(int i = 0; i < n; i ++){if(out[i] == 1)// 先让出度为1的点入队{q.push(i);}}while(q.size()){res.clear();// res 存储当下遍历完的节点int num = q.size();for(int i = 0; i < num; i ++){int x = q.front();q.pop();res.push_back(x);for(auto it : e[x]){out[it] --;// 与该点连接的点 出度减一if(out[it] == 1)// 添加新的"叶子节点"{q.push(it);}}}}return res;}
};

思路来自 大佬小鑫