给定一棵自由树,找到一种算法来找到两个节点之间以线性时间运行的最长路径。如果节点不存储它们的级别,是否可以这样做?如果是,如何?
如果节点确实存储了它们的级别,那么我会将较低的节点向上移动到与其他节点相同的级别。比我会继续向上移动树直到节点重叠。距离将是节点在树中向上移动的每次总和。
最佳答案
如果两个节点之间的所有边都不能被多次使用,则路径是固定的。所以问题是找到最低的共同祖先,你可以在这里阅读:http://en.wikipedia.org/wiki/Lowest_common_ancestor 有一个著名的算法可以解决它,就在这里: http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm
关于algorithm - 用于查找自由树中两个节点之间最长距离的线性时间算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9797084/