文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

求樹的最大直徑。

2. 解題

類似題目：LeetCode 5538. 統(tǒng)計(jì)子樹中城市之間最大距離（枚舉所有可能+圖的最大直徑）

• 結(jié)論：求無權(quán)無向圖中的最長一條路徑
  先從任意一點(diǎn)P出發(fā)，找到離它最遠(yuǎn)的點(diǎn)Q
  再從點(diǎn)Q出發(fā)，找離它最遠(yuǎn)的點(diǎn)W，W到Q的距離就是最長的一條路

• 采用2次BFS遍歷

class Solution { public:int treeDiameter(vector<vector<int>>& edges) {int n = edges.size()+1;unordered_map<int,unordered_map<int,bool>> m;for(auto& e : edges){m[e[0]][e[1]] = 1;m[e[1]][e[0]] = 1;}int a,cur,size,step = 0;queue<int> q;vector<bool> visited(n,false);q.push(0);visited[0] = true;while(!q.empty()){cur = q.front();q.pop();a = cur;//記錄最后到達(dá)的點(diǎn)afor(auto it = m[cur].begin(); it != m[cur].end(); ++it){if(!visited[it->first]){q.push(it->first);visited[it->first] = true;}}}vector<bool> visited1(n,false);q.push(a);//從a出發(fā)，到達(dá)的最遠(yuǎn)的就是最大的路徑visited1[a] = true;while(!q.empty()){size = q.size();while(size--){cur = q.front();q.pop();for(auto it = m[cur].begin(); it != m[cur].end(); ++it){if(!visited1[it->first]){q.push(it->first);visited1[it->first] = true;}}}step++;}return step-1;} };

136 ms 24.4 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1245. 树的直径（图的最大直径结论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。