首页 > 试题广场 >

多叉树的直径

[编程题]多叉树的直径
  • 热度指数：10679 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一棵多叉树，求出这棵树的直径，即树上最远两点的距离。
包含n个结点，n-1条边的连通图称为树。
示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11

数据范围：，保证最终结果满足
要求：空间复杂度：，时间复杂度
示例1

输入

6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]

输出

11
示例2

输入

2,[[0,1],[1,2]],[1]

输出

1
算法知识视频讲解
开通博客
头像 有名
发表于 2021-07-17 11:29:29
精华题解 方法一： 思路 题目中有提到连通图，所以就想着将给的数据转换成无向图，再遍历无向图找到一条最长路径，使用邻接矩阵存储无向图。 具体步骤 首先将所给数据转换成图，由所给例子可以看出，其是个无向图，故，转换成无向图时，需要将(i,j)与(j,i)同时设置为边对应的权重； 以每一个节点为起点，去计算以当 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 SandMonth
发表于 2021-08-08 22:22:46
树都直径给定一棵树，求出这棵树的直径，即树上最远两点的距离。 案例输入：6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]返回值：11案例说明:选择4点到5点的距离,距离为5+2+4=11，为距离最长 方法一 树上dp 1.对一颗树从叶子结点向根遍历2. 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 xqxls
发表于 2021-12-18 22:33:21
题意整理 给定一棵树，求出这棵树的直径，即树上最远两点的距离。 方法一（dfs） 1.解题思路 首先初始化邻接表，以边的起点为索引，将对应的边的终点以及边的权值放在该索引对应的list里。 先从0号节点进入递归，通过递归找到当前节点所能到达的最远节点，跟新最远节点的规则是路径权值和大于之前的权 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 junex
发表于 2021-03-27 20:52:12
import java.util.*; public class Solution { class Node{ // 邻接点结构 int id, dist; //id表示节点编号，dist表示距离 public Node(){} public 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 godhands
发表于 2022-02-12 16:53:34
描述 题目描述 这个题目是一道很不错的题目, 先是给了我们一颗树, 让我们求取树上最远点两个点的距离比如这样的一颗树 我们发现从444到555的权值是最大的, 所以我们输出他们的权值 然后我们仔细思考这个, 他没有规定我们应该是从哪一个点到哪一个点, 那么我们就是可以把他当成一个无向图来做, 这样 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 zcr214
发表于 2021-12-10 16:46:33
本题最大的麻烦之处在于输入是离散的一条条边，没有直接保存节点，需要从这些边当中提取节点的信息，从而将他们处理成树的关系，即：要保存节点，以及节点之间的边长 由于不是二叉树，每个节点的子节点可能存在多个，则需要用一个二维的结构来保存树。 然后再使用“二叉树中的最大路径和”的结题思路，采取动态规划算法即 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 HuiPuKui
发表于 2024-01-01 20:44:48
/** * struct Interval { * int start; * int end; * Interval(int s, int e) : start(start), end(e) {} * }; */ // 求树的直径，一次 dfs 即可，每次记录最大值、次大值，即以当前节 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 红骚鱼
发表于 2022-05-19 17:20:54
思路就是通过两次DFS/BFS确定多叉树(无向无环无负权图)的直径，这里提供java的两个版本，参考评论区的各位dalao([狗头保命])。 DFS: import java.util.*; /*  * public class Interval 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 XingHe_XingHe
发表于 2021-09-07 12:03:10
描述给定一棵树，求出这棵树的直径，即树上最远两点的距离。包含n个结点，n-1条边的连通图称为树。示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11 例1输入：6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]复制返回值：11 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-18 22:33:10
思路： 题目的主要信息： 要求树的直径，即树上两点最远距离 这里的树不止是二叉树，都有可能 题目给的Tree_edge是一个点到另一个点有边，Edge_value为与之对应的边的权重weigh 方法一：两次深度优先搜索 首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 DataTailor
发表于 2023-06-09 10:09:04
思路：对于任意节点，计算最远节点距离和第二远节点距离，两距离之和是通过当前节点的最远路径。直径即通过每个节点的最远路径的最大值。使用递归方法遍历整个树，在递归函数中同时完成距离的计算与通过当前节点最远路径的计算和比较 # class Interval: # def __init__(self 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

图
上传者：牛客332641号
难度：
41条回答 8677浏览

热门推荐

通过挑战的用户

查看代码

相关试题

多叉树的直径

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号