题目描述
给定一棵树，求出这棵树的直径，即两个节点距离的最大值。
题解：
不知道大家听没听过一个结论：
树的直径可以通过两边dfs找到
步骤：
1.从任意一点进行dfs，然后找到一个最长路径，记录最远点u
2.然后从u再进行dfs，找最长路径，记录一点v。
（u，v）就是树的直径
证明：
我们可以看出图中，树的直径是（4->2->5），长度为9.
我们一开始选定一个点dfs
如果是直径外一点，比如w1，从w1进行dfs找到的就是点4，路径就1->2->4，这个路径一定会与树的直径相交，而找到的4是直径的一端，那从4再进行dfs就是树的直径的另一端5，这样两遍dfs你就找到了树的直径
如果是直径内一点，比如w2，从w2开始dfs找到的最远点4，这个路径会被包含在树的直径里，那找到的点也就是树直径的一端，再dfs就可以找到另一端。
综上用两遍dfs就可以找到树的直径
其实求直径也就是求深度，所以我们dfs直接求树的深度，并记录最大深度，以及对应的节点，然后再带入到第二遍dfs即可
代码：
/** * struct Interval { * int start; * int end; * }; */
class Solution {
public:
/** * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类vector 树的边 * @param Edge_value int整型vector 边的权值 * @return int整型 */int far,Max;
vector<vector<pair<int,int> >>G;
void dfs(int u,int deep,int fa)
{
if(deep>Max)
{
far=u;
Max=deep;
}
for(auto &it:G[u])
{
int v=it.first;
int w=it.second;
if(v==fa)continue;
dfs(v,deep+w,u);
}
}
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
G.clear();
G.resize(n + 1);
for (int i = 0; i < n - 1; ++i) {
Interval e = Tree_edge[i];
int w = Edge_value[i];
int u=e.start;
int v=e.end;
G[u].push_back(pair<int,int>(v, w));
G[v].push_back(pair<int,int>(u, w));
}
far = 1; Max = 0;
dfs(1, 0, 0);
dfs(far, 0, far);
return Max;
}
};
京公网安备 11010502036488号