之前的
那天我用抄的
最近練習比較多圖
回來再寫一次
題目:
有一棵沒有迴圈的樹
如果讓你拿一個節點當樹頂
讓他的層數最少 最矮
請問要拿哪些節點
思路:
拿最中間那幾個
就可以讓他最矮
沒有迴圈這點很重要
代表可以用拓樸排序整理節點的層數
我用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]