题目描述
给你这棵「无向树」,请你测算并返回它的「直径」:这棵树上最长简单路径的 边数。
我们用一个由所有「边」组成的数组 edges 来表示一棵无向树,其中 edges[i] = [u, v] 表示节点 u 和 v 之间的双向边。
树上的节点都已经用 {0, 1, …, edges.length} 中的数做了标记,每个节点上的标记都是独一无二的。
样例
样例1 图示
输入:edges = [[0,1],[0,2]]
输出:2
解释:
这棵树上最长的路径是 1 - 0 - 2,边数为 2。
样例2图示
输入:edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出:4
解释:
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5,边数为 4。
算法1
求无向树最远距离 分为两步
1 任选一点 BFS或者DFS获取离该点最远的点
2 以第一步得到的点为起点 再次BFS或者DFS获取距离最远的点。两者距离就是最远距离
C++ 代码
class Solution {
public:
pair<int, int> bfs(vector<vector<int>>& e, int start) {
vector<int> d(e.size(), -1);
queue<int> Q;
Q.push(start);
d[start] = 0;
pair<int, int> ret;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
ret.first = x;
ret.second = d[x];
for (auto& y : e[x]) {
if (d[y] == -1) {
d[y] = d[x] + 1;
Q.push(y);
}
}
}
return ret;
}
int treeDiameter(vector<vector<int>>& edges) {
int n = edges.size() + 1;
vector<vector<int>> e(n, vector<int>());
for (auto& edge: edges) {
e[edge[0]].push_back(edge[1]);
e[edge[1]].push_back(edge[0]);
}
pair<int, int> p;
p = bfs(e, 0);
p = bfs(e, p.first);
return p.second;
}
};