首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >找到树的节点之间的最大距离?有人能给我解释一下这个方法吗?

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

Stack Overflow用户
提问于 2021-09-04 09:38:29
回答 1查看 2K关注 0票数 0

链接到问题

问题的InterviewBit解决方案

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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;
}

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

  1. 选择任何节点u。
  2. 找到离u最远的节点,叫它x。
  3. 找到离x最远的节点,称之为q。
  4. 答案是从x到q的路径的长度。
EN

回答 1

Stack Overflow用户

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

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

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

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

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

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

操作步骤:

  1. 从一个随机节点(假设我们从根节点运行)启动BFS,并找出离它最远的节点。让最远的节点是X,很明显,X永远是一个叶节点。
  2. 现在,如果我们从X开始BFS并检查离它最远的节点(就像我们以前做的那样),我们将得到树的直径。

样本代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#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;
}

参考资料:

使用DFS的树的直径

用DFS证明求树的直径

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/69057644

复制
相关文章
如何在 Git 上更改分支名称?
在 Git 版本控制系统中,分支是非常重要的概念。分支允许你在项目中进行并行开发和实验,同时保持主分支的稳定性。有时候,你可能需要更改已存在的分支名称,例如纠正拼写错误或者为了更好地描述分支的内容。本文将详细介绍如何在 Git 上更改分支名称。
网络技术联盟站
2023/06/19
1.9K0
如何在 Git 上更改分支名称?
更改Linux网卡名称
转载自:https://blog.csdn.net/yeziand01/article/details/88424624
zy010101
2019/07/02
5.1K0
更改Linux网卡名称
Oracle 更改表名称的几种方式
ALTER TABLE old_table_name RENAME TO new_table_name;(大写为系统命令)
全栈程序员站长
2022/08/29
4.7K0
更改WordPress插件的菜单名称
如果您想在不直接编辑插件的情况下更改WordPress内部管理菜单的名称,您可以使用$menuWordPress管理员中存在的全局变量。操作此数据结构将允许您更改由任何插件添加的管理菜单的文本或名称。这在您希望提供项目内容的清晰度或为客户端提供更好的管理UX的情况下非常有用。
许都博客
2021/06/15
4K0
Github更改账户名称/仓库地址/个人链接后缀
注意:在public profile中修改的name,是主页个人名字,不是仓库地址后缀!!!
浩Coding
2019/07/03
11.4K0
如何在NLP中有效利用Deep Transformer?
2017年,谷歌在“Attention is all you need”一文中首次提出了完全基于self-attention(自注意力)机制的transformer模型,用于处理序列模型的相关问题,如机器翻译等。传统的神经机器翻译模型大都是采用RNN或者CNN作为encoder-decoder模型的基础,而Transformer模型则摒弃了固有的模式,采用完全并行化的结构,在提升了模型的性能的同时提高了训练的速度,目前已经被推广到多项自然语言处理的相关任务当中。
AI科技评论
2020/02/14
9570
如何在NLP中有效利用Deep Transformer?
如何在Linux中更改SSH端口?
SSH(Secure Shell)是一种安全的远程登录协议,它允许您通过网络远程连接到Linux系统并进行管理操作。默认情况下,SSH使用22端口进行通信。然而,为了增强系统的安全性,有时候我们需要更改SSH端口,以减少潜在的攻击。
网络技术联盟站
2023/05/25
9.4K0
如何在Linux中更改SSH端口?
如何在 Linux 中更改主机名?
在 Linux 系统中,主机名是用于标识和区分网络上的不同计算机的名称。默认情况下,Linux 发行版会分配一个主机名给您的计算机,但是有时候您可能需要根据自己的需求更改主机名。在本文中,我们将详细介绍如何在 Linux 中更改主机名,以及更改主机名后可能涉及到的其他配置。
网络技术联盟站
2023/06/09
8.8K0
如何在 Linux 中更改主机名?
linux中有选择的删除目录中的文件
某些场景下我们需要删除目录下指定类型,后缀的文件。这时候就需要一些小技巧。 首先我们先要了解一下模式匹配。在Linux中,shell模式是由以下特殊字符组成的字符串,称为wildcards或者meta
入门笔记
2022/06/02
3K0
如何在 Linux 中更改 Nginx 80 端口?
Nginx 是一个开源的轻量级 Web 服务器替代 apache 来处理高流量的网站。
网络技术联盟站
2022/06/21
5.4K0
如何在 Linux 中更改 Nginx 80 端口?
如何在Ubuntu 14.04上更改PHP设置
PHP是一种服务器端脚本语言,被许多流行的CMS和博客平台使用,如WordPress和Drupal。它也是流行的LAMP和LEMP堆栈的一部分。在设置基于PHP的网站时,更新PHP配置设置是一项常见任务。找到确切的PHP配置文件可能并不容易。有多个PHP安装在服务器上正常运行,每个安装都有自己的配置文件。知道要编辑哪个文件以及当前设置是什么可能有点神秘。
彼岸轮回
2018/09/25
1.7K0
如何在 Linux 中更改 Apache HTTP 端口?
Apache Web Server 是一个免费的开源跨平台 Web 服务器应用程序,用于通过 Internet 提供内容。
网络技术联盟站
2022/06/21
6.3K0
如何在 Linux 中更改 Apache HTTP 端口?
如何在Linux中更改用户ID?
在Linux系统中,每个用户都有一个唯一的用户ID(User ID),用于标识和管理用户的权限和资源访问。有时候,我们需要更改用户ID,可能是为了解决冲突、重组用户组或其他管理需求。本文将详细介绍如何在Linux中更改用户ID的几种方法。
网络技术联盟站
2023/06/08
8.4K0
如何在Linux中更改用户ID?
使用Python实现批量更改文件夹下图片的名称
前几天在Python白银交流群有个叫【belongs】的粉丝问了一个使用Python实现批量更改文件夹下图片的名称的问题,如下图所示。
前端皮皮
2022/08/17
2.6K0
使用Python实现批量更改文件夹下图片的名称
点击加载更多

相似问题

在CKEditor中有选择地触发更改事件

12

如何在Coq中有选择地重写?

15

选择名称匹配,如80%

35

如何在FosUserbundle中有选择地禁用注册?

22

如何在python中有选择地深拷贝?

11
添加站长 进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

扫码加入开发者社群
关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

扫码关注腾讯云开发者公众号
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文