我有一棵树和 3 个节点 A
、B
、C
。问题是找到 的路径大小>A
和 B
将共享到 C
的最短路径。
有3种情况:
当
C
是A
和B
的祖先时。在本例中,答案是min(深度(A), 深度(B)) - 深度(C)
当
C
是A
的祖先但不是B
时,反之亦然。在本例中,答案是1
,只是节点C
当
A
和B
都不是C
的后代时,我无法弄清楚这种情况。
我会有很多疑问,所以我需要一种有效的方法。不考虑我们可以在 O(logN)
中获得每个 LCA,每个查询都应该是 O(1)
。
最佳答案
如DAle pointed out在上面的答案中,一种方法可以基于他所说的方式,即将树的根设为C
,然后检查路径。
另一种方法可以用类似的方式找到 A 和 B 的最低公共(public)后代 (LCD)。简而言之,我们可以找到 A 和 B 的路径的第一个节点B 会在走向 C 时与相交,然后给出从该节点到 C 的路径的大小。那么可能有几种情况:
- A 和 B(前往 C)的 LCD 为 A:从 A 到 C 的路径返回长度
- A 和 B(前往 C)的 LCD 为 B:从 B 到 C 的路径返回长度
- A和B(往C方向)的LCD为C:返回0
- A和B(去C)的LCD是节点D:返回从D到C的路径长度
关于algorithm - 树中的共享路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45410568/