之前的 那天我用抄的 最近練習比較多圖 回來再寫一次 題目: 有一棵沒有迴圈的樹 如果讓你拿一個節點當樹頂 讓他的層數最少 最矮 請問要拿哪些節點 思路: 拿最中間那幾個 就可以讓他最矮 沒有迴圈這點很重要 代表可以用拓樸排序整理節點的層數 我用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]--; if(one[go] == 0) { //cout << "my go !!!!!"; paper.push({go,k.second+1}); } } } vector<int> res; int k = 0; for(int i = 0 ; i < n ; i ++) { //cout<<layer[i]<<" "; k = max(k,layer[i]); } for(int i = 0 ; i < n ; i ++) { if(layer[i] == k)res.push_back(i); } return res; } }; ``` -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.27.25 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722310288.A.80E.html