algorithm - 查找树中节点集之间的最长路径

Question

最近碰到一道编程题。

给定一棵树，可以是非二叉树，可以是单链(或线性)，有 N 个节点。

输入将是一组 K 个节点，表示为 a1,a2....ak。我想找到最长的简单路径，该路径从这些 K 个节点之一开始，并在这些 K 个节点之一(不同于起始节点)处结束。依赖于 N 或 K 的对数算法应该满足运行时间要求(例如:KlogK，KlogN)，如果需要的话应该在我想要的时间限制内。

谢谢

Answer 1

也许你可以试试这个方法——

1. 从任何节点运行 DFS 以找到最远的叶节点，我们称它为节点 X。
2. 运行另一个 DFS 以找到距 X 最远的节点。
3. 您在第 2 步中找到的路径是树中最长的路径。

这应该适用于所有树，而不仅仅是二叉树。