algorithm - 如何判断节点w是否位于树中节点u和节点v之间的路径上？

Question

我正在尝试解决一个问题，该问题需要我确定节点 w 是否位于树中节点 u 和节点 v 之间的路径上(不一定是二叉树)。

例如，对于下面的树:

    1
  2   3
4  5 6  7

节点 2 位于节点 4 到 7 的路径上。

一个明显的解决方案是获得树的欧拉之旅并遍历在两个节点的第一次出现之间访问过的节点。但是，在最坏的情况下，这将是一个 O(n) 解决方案，其中 n 是树中的节点数。我在某处读到这可以使用 LCA(最低公共(public)祖先)来完成。但是，我似乎无法理解如何。有人可以给我建议吗？

Answer 1

假设 A = LCA(u,v)。 u 和 v 之间的路径是从 u 到 A 和从 A 到 v 的路径。检查这些节点中的每一个(从 u 向上，然后从 v 向上)。如果 w 在其中，则它在路径上，否则它不在。