问找到树的节点之间的最大距离？有人能给我解释一下这个方法吗？
EN

Stack Overflow用户

提问于 2021-09-04 09:38:29

回答 1查看 2K关注 0票数 0

链接到问题

问题的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;
}

有人能向我解释一下上面的代码以及他们的方法吗?他们说：

选择任何节点u。
找到离u最远的节点，叫它x。
找到离x最远的节点，称之为q。
答案是从x到q的路径的长度。

graph-algorithm

c++

algorithm

graph

tree

云联络中心6.1折起

灵活稳定的一体化云联络中心，助力快速搭建集电话、在线交流、音视频通话为一体的客户联络平台

回答 1

Stack Overflow用户

发布于 2021-09-04 13:03:15

基本上问题是找出一棵树的直径。

树的直径--它是树中两个节点之间最长的路径。

最长路径总是发生在两个叶节点之间。

假设，从给定的数组中，您已经创建了树。

现在您可以使用2个DFS或BFS来完成它。

操作步骤：

从一个随机节点(假设我们从根节点运行)启动BFS，并找出离它最远的节点。让最远的节点是X，很明显，X永远是一个叶节点。
现在，如果我们从X开始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;
}