1. 问题描述
- 给定一棵树，求树中最长的路径的长度，也就是树的直径；
- 该树的节点数为
，编号为
；
- 定义树中某一个节点
的相邻节点为
；
2. 求解方法
- 从
；
- 在树中找一条以
- 假设找到的路径的另外一个端点为
，那么树中以
3. 证明
假设一颗树如下图所示：
树
再假设，第一个节点选择的是 节点 ，以 节点
为起点的最长的路径是
。基于上述假设，要证明上述方法正确，即证明：
- 节点
或
是某条最长路径的一个端点。
要证明上述结论，假设某一个节点 是树中某一个最长路径的端点，该路径为
，有如下结论：
- 节点
不是
中的一个（不包括节点
-
与
重叠一边，且重叠部分为靠近 节点
- 如果
这种路径，此时可以找到比
- 如果
- 如果
上述例子可以扩展成一般的情况。因此，上述结论成立，从而上述方法正确。
4. 给定某一个节点求解树中离这个节点最远的节点以及对应路径长度
使用DFS可以解决这个问题。
定义 dfs(v) 的含义为，返回范围以 节点 为根的子树中距离最远的节点以及对应的长度。
def dfs(v):
max_dis = 0
max_node = v
for u in child(v):
update_node, update_dis = dfs(u) + 1
if update > max_dis:
max_dis = update_dis
max_node = update_node
return max_node, max_dis
通过上述递归的方法就可以求出对应的节点，以及具体的距离。
