线性时间算法查找在自由树的两个节点之间的最大距离？ [英] A linear-time algorithm for finding the longest distance between two nodes in a free tree?

问题描述

给定一个自由树，找到一种算法来发现运行在时间的线性两个节点之间的最长的路径。这是可以做到的，如果节点不保存自己的水平？如果是的话，怎么办？

Given a free tree, find an algorithm to find the longest path between two nodes that runs in linear time. Is this possible to do if the nodes don't store their level? If yes, how?

如果节点做存储自己的水平，那么我会树移到下层节点到同一水平的其他。比我会继续前进了树，直到节点重叠。的距离将是一个节点被移动向上树中每个时间的总和。

If the nodes do store their level then I would move the lower node up the tree to the same level as the other. Than I would keep moving up the tree until the nodes overlap. The distance would be the sum of each time a node was moved up the tree.

推荐答案

如果两个节点之间的所有的边不能被使用一次以上，该​​路径是固定的。所以，问题是要找到最低的共同祖先，你可以在这里阅读： http://en.wikipedia.org /维基/ Lowest_common_ancestor 有一个著名的算法来解决它，它在这里： 的http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm

If all the edges between the two nodes could not be used more than once, the path is fixed. So the problem is to find the lowest common ancestor, you can read here: http://en.wikipedia.org/wiki/Lowest_common_ancestor There's a famous algorithm to solve it, and it's here: http://en.wikipedia.org/wiki/Tarjan%27s_off-line_least_common_ancestors_algorithm

这篇关于线性时间算法查找在自由树的两个节点之间的最大距离？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！