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

Question

最近遇到一个编程问题。

给定一棵树，可以是非二元的，可以是单链（或线性），具有 N 个节点。

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

谢谢

Answer 1

也许您可以尝试这种方法-

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

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