1245. Tree Diameter
premium題 找出一個tree的最長path
看起來不太直覺 其實只是實作一個找depth的function
同時記下前兩深的subtree的深度 同時更新最長path長度
最長path必會是某個root的兩個最深subtree的深度相加再+2
DFS的過程就可以順便更新
寫起來不難 但不熟的話一開始會卡:( 希望有記起來
class Solution {
public:
int helper(unordered_map<int, vector<int>>& g, int root, int parent, int*
ans)
{
// calculate depth
int max_depth_1 = -1, max_depth_2 = -1;
for(auto n : g[root])
{
if(n != parent)
{
max_depth_2 = max(max_depth_2, helper(g, n, root, ans));
if(max_depth_2 > max_depth_1) swap(max_depth_1, max_depth_2);
}
}
// update ans
*ans = max(*ans, max_depth_1+max_depth_2+2);
// return depth
return max_depth_1+1;
}
int treeDiameter(vector<vector<int>>& edges) {
unordered_map<int, vector<int>> g;
for(auto e : edges)
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
int ans = 0;
int depth = helper(g, 0, -1, &ans);
return ans;
}
};