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;
}
};