algorithm - 树中的共享路径

Question

我有一棵树和 3 个节点 A、B、C。问题是找到 的路径的大小>A 和 B 将共享到 C 的最短路径。

有3种情况:

1. 当C 是A 和B 的祖先时。在这种情况下，答案是 min(depth(A), depth(B)) - depth(C)

2. 当 C 是 A 而不是 B 的祖先时，反之亦然。在这种情况下，答案是1，只是节点C

3. 这是一个我无法弄清楚 A 和 B 都不是 C 的后代的情况。

我会有很多疑问，所以我需要一种有效的方法。尽管我们可以在 O(logN) 中获取每个 LCA，但每个查询都应该是 O(1)。

Answer 1

作为DAle pointed out在上面的答案中，一种方法可以基于他所说的方式，即通过将树的根设为 C 然后检查路径。

另一种方法是以类似的方式找到 A 和 B 的Lowest Common Descendant (LCD)。简而言之，我们可以找到 A 和 B 的路径所在的第一个节点B 将在走向 C 时相交，然后给出从该节点到 C 的路径的大小。然后可能有几种情况:

1. A 和 B(向 C 方向)的 LCD 为 A:从 A 到 C 的路径返回长度
2. A 和 B(朝向 C)的 LCD 为 B:从 B 到 C 的返回路径长度
3. A和B(向C方向)的LCD为C:返回0
4. A和B(去往C)的LCD是一个节点D:从D到C的返回路径长度