元戎启行一面凉

自我介绍 聊项目
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届毕业生现状#