algorithm - 树中的共享路径

标签 algorithm tree path-finding

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

有3种情况:

  1. CAB的祖先时。在本例中,答案是 min(深度(A), 深度(B)) - 深度(C)

  2. CA的祖先但不是B时,反之亦然。在本例中,答案是 1,只是节点 C

  3. AB 都不是 C 的后代时,我无法弄清楚这种情况。

我会有很多疑问,所以我需要一种有效的方法。不考虑我们可以在 O(logN) 中获得每个 LCA,每个查询都应该是 O(1)

最佳答案

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

另一种方法可以用类似的方式找到 A 和 B 的最低公共(public)后代 (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的路径长度

关于algorithm - 树中的共享路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45410568/

相关文章:

c - 将错误文本与 C 中的错误代码相关联

算法题

java路径从网格的顶部到底部

ios - 视觉节点之间的视觉寻路

R实现聚类分析

algorithm - 用函数解析表达式

mysql - 原始树集上的嵌套连接

C++ 递归函数中的平衡树/调用顺序

algorithm - 合适的树数据结构

unity3d - 如何避免两个 NavMeshAgent 在 Unity 中相互推开?