快速的网站建设,重庆做学校网站公司,阿里虚拟机建设网站,建筑管理招聘网目录 一.题目原型
二.题目思路
三.代码实现 一.题目原型 二.题目思路 首先#xff0c;我们看了样例#xff0c;发现这个树并不是二叉树#xff0c;是多叉树。 然后#xff0c;我们可能想到的解法是#xff1a;根据题目的意思#xff0c;就挨个节点遍历bfs#xff0c;…目录 一.题目原型
二.题目思路
三.代码实现 一.题目原型 二.题目思路 首先我们看了样例发现这个树并不是二叉树是多叉树。 然后我们可能想到的解法是根据题目的意思就挨个节点遍历bfs统计下每个节点的高度然后用map存储起来后面查询这个高度的集合里最小的就可以了。 但是这样会超时的。 于是我们看图题目介绍里面的图分析一下发现越是靠里面的节点越有可能是最小高度树。 所以我们可以这样想我们可以倒着来。 我们从边缘开始先找到所有出度为1的节点然后把所有出度为1的节点进队列然后不断地bfs最后找到的就是两边同时向中间靠近的节点那么这个中间节点就相当于把整个距离二分了那么它当然就是到两边距离最小的点啦也就是到其他叶子节点最近的节点了。 然后就可以写代码了。 三.代码实现 1.通过遍历 edges 构建度数表和邻接图 2.每次把度数为 1 的节点加入队列 3.广度遍历队列把邻接图中的节点度数减一当其度数为1时将其入队 4.res数组每一层都更新一次所以最后一次保留的就是使得高度最小的节点 class Solution {
private:// 找最小高度最短路径想到BFS// 两端烧香求中点
public:vectorint findMinHeightTrees(int n, vectorvectorint edges) {if (n 1) return {0};vectorint res; // 每个节点的度数vectorint degree(n);// 建立无向邻接图vectorvectorint map(n);for (int i 0; i edges.size(); i) {int v1 edges[i][0];int v2 edges[i][1];degree[v1];degree[v2];map[v1].push_back(v2);map[v2].push_back(v1);}// 把度为1的节点入队queueint q;for (int i 0; i n; i) {if (degree[i] 1) q.push(i);}// BFSwhile (!q.empty()) {// 清理当前层的节点res.clear();int size q.size();while (size--) {int cur q.front();q.pop();res.push_back(cur);// 减小对应度数degree[cur]--;for (auto i : map[cur]) {degree[i]--;if (degree[i] 1) {q.push(i);}}}} return res;}
};
