2023-07-27 22:59 华中科技大学 机器学习
关注
元戎启行一面凉
自我介绍 聊项目
2.手撕代码
遍历一棵N个点的树，需要选一个起点，遍历整棵树，计算走的路径长度最短为多少。
输入: N N-1条长度为1的边，表示为(a,b)
输出: 2
N<100；
N<1000；
N<100000;
例子： 1-2 2-3 可能的长度是2和3，所以答案是2.
思路：
在这个问题中，给定的是一棵N个节点的树，每个边的长度均为1。问题要求找到一个起点，通过这个起点遍历整棵树的路径长度最短为多少。
一棵树的遍历问题中，如果所有边的长度相等，那么遍历全树的最短路径长度就等于2*(N-1) - h，其中h是树的高度。因为在遍历过程中，每一个节点（除了根节点）都需要被访问两次（一次进，一次出），所以总路径长度至少是2*(N-1)。然后我们可以减去树的高度h，因为在从根节点到最深的叶节点这段路径中，每个节点只被访问了一次。
所以，为了得到最短的路径长度，我们需要选择一个使树高度最小的节点作为起点。这个节点就是树的中心点，也就是树的直径的两个端点。树的直径可以通过以下步骤计算：
1. 从任意一个节点开始，进行深度优先搜索（DFS），找到距离这个节点最远的节点A。
2. 从节点A开始，进行深度优先搜索，找到距离节点A最远的节点B。那么，节点A到节点B的距离就是树的直径。
3. 选择节点A和节点B中的任意一个作为起点，遍历整棵树，就能得到路径长度最短的结果。
这个算法的时间复杂度是O(N)，因此对于N<100, N<1000, N<100000的输入，都能在可接受的时间内得到结果。 #2024届校园招聘# #元戎启行2024秋招# #2022届毕业生现状#
2.手撕代码
遍历一棵N个点的树，需要选一个起点，遍历整棵树，计算走的路径长度最短为多少。
输入: N N-1条长度为1的边，表示为(a,b)
输出: 2
N<100；
N<1000；
N<100000;
例子： 1-2 2-3 可能的长度是2和3，所以答案是2.
思路：
在这个问题中，给定的是一棵N个节点的树，每个边的长度均为1。问题要求找到一个起点，通过这个起点遍历整棵树的路径长度最短为多少。
一棵树的遍历问题中，如果所有边的长度相等，那么遍历全树的最短路径长度就等于2*(N-1) - h，其中h是树的高度。因为在遍历过程中，每一个节点（除了根节点）都需要被访问两次（一次进，一次出），所以总路径长度至少是2*(N-1)。然后我们可以减去树的高度h，因为在从根节点到最深的叶节点这段路径中，每个节点只被访问了一次。
所以，为了得到最短的路径长度，我们需要选择一个使树高度最小的节点作为起点。这个节点就是树的中心点，也就是树的直径的两个端点。树的直径可以通过以下步骤计算：
1. 从任意一个节点开始，进行深度优先搜索（DFS），找到距离这个节点最远的节点A。
2. 从节点A开始，进行深度优先搜索，找到距离节点A最远的节点B。那么，节点A到节点B的距离就是树的直径。
3. 选择节点A和节点B中的任意一个作为起点，遍历整棵树，就能得到路径长度最短的结果。
这个算法的时间复杂度是O(N)，因此对于N<100, N<1000, N<100000的输入，都能在可接受的时间内得到结果。 #2024届校园招聘# #元戎启行2024秋招# #2022届毕业生现状#
全部评论
A码农烧烤
门头沟学院 研发工程师
m
哥别挂我了哥
轻舟智航_感知_感知融合
我靠，好难的面试
奶茶七分糖
腾讯_游戏策划
撕出来还凉吗
牛客460271859号
门头沟学院 机器学习
所以请问这个题是力扣847吗
就很离谱啊
门头沟学院 C++
码一下
大逗比👀
门头沟学院 C++
是不是和力扣的 847. 访问所有节点的最短路径 一样？
淘气的哈士奇在发动态 楼主
楼主 华中科技大学 机器学习
欢迎大家来探讨一下这道算法题
Crossea
字节跳动_后端开发
哥们你这不对吧，你仔细看式子是减h，所以不应该是选择h最高的吗
牛客506733970号
门头沟学院 算法工程师
兄弟面的哪个岗
相关推荐
点赞 评论 收藏
分享
