问题的InterviewBit解决方案
int Solution::solve(vector<int> &A)
{
vector<int> hgt(A.size(),0);
int ans=0,maxx=0;
for(int i=A.size()-1;i>0;i--)
{
ans=max(ans,hgt[A[i]]+hgt[i]+1);
hgt[A[i]]=max(hgt[i]+1,hgt[A[i]]);
}
return ans;
}
有人能向我解释一下上面的代码以及他们的方法吗?他们说:
发布于 2021-09-04 13:03:15
基本上问题是找出一棵树的直径。
树的直径--它是树中两个节点之间最长的路径。
最长路径总是发生在两个叶节点之间。
假设,从给定的数组中,您已经创建了树。
现在您可以使用2个DFS或BFS来完成它。
操作步骤:
样本代码:
#define MAX 40001
vector<int> adj[MAX];
int dist[MAX];
int totalNode;
pair<int, int> _bfs(int startingNode) {
for(int i=0; i <= totalNode; i++) {
dist[i] = 0;
}
dist[startingNode] = 1;
int maxDistance = 0, farthestNode;
queue<int> q;
q.push(startingNode);
while(!q.empty()) {
int currNode = q.front();
q.pop();
int sz = adj[currNode].size();
for(int i = 0; i < sz; i++) {
int nextNode = adj[currNode][i];
if(dist[nextNode] == 0) {
dist[nextNode] = dist[currNode] + 1;
q.push(nextNode);
if(dist[nextNode] > maxDistance) {
maxDistance = dist[nextNode], farthestNode = nextNode;
}
}
}
}
return {farthestNode, maxDistance};
}
int _getDiameter(int &rootNode) {
// Running the first BFS from the root node (as explained in the procedue 1)
pair<int, int> pii = _bfs(rootNode);
// Running the second BFS from the furthest node we've found after running first BFS (as explained in the procedure 2)
pair<int, int> pii2 = _bfs(pii.first);
return pii2.second;
}
int Solution::solve(vector<int> &A) {
totalNode = A.size();
int rootNode;
if(totalNode == 1) return 0;
if(totalNode == 2) return 1;
for(int i = 0; i < totalNode; i++) adj[i].clear();
for(int i = 0; i < totalNode; i++) {
int n = A[i];
if(n == -1) rootNode = i;
else adj[i].push_back(n), adj[n].push_back(i);
}
return _getDiameter(rootNode) - 1;
}
参考资料:
https://stackoverflow.com/questions/69057644
复制相似问题