之前的
那天我用抄的
最近练习比较多图
回来再写一次
题目:
有一棵没有循环的树
如果让你拿一个节点当树顶
让他的层数最少 最矮
请问要拿哪些节点
思路:
拿最中间那几个
就可以让他最矮
没有循环这点很重要
代表可以用拓朴排序整理节点的层数
我用khan的方法来找出大家的层数
从外圈bfs到内圈
然后找出最中间的那几个
```cpp
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges)
{
if(n == 1)return {0};
if(n == 2)return {0,1};
int len = edges.size();
vector<int> one(n,-1);
vector<int> visited(n,0);
unordered_map<int,vector<int>> save;
vector<int> layer(n,0);
for(int i = 0; i < n-1 ; i ++)
{
one[edges[i][0]]++;
one[edges[i][1]]++;
save[edges[i][0]].push_back(edges[i][1]);
save[edges[i][1]].push_back(edges[i][0]);
}
queue<pair<int,int>> paper;
for(int i = 0 ; i < n ; i ++)
{
if(one[i] == 0)
{
visited[i] = 1;
paper.push({i,1});
}
}
while(!paper.empty())
{
pair<int,int> k = paper.front();
paper.pop();
layer[k.first] = k.second;
for(int go : save[k.first])
{
one[go]