2

给定一棵树，我需要在从“a”到“b”的路径中找到第“k”个节点。这意味着我需要在从节点'a'到节点'b'的路径中的'kth'位置找到节点。我在考虑最低共同祖先和/或重光分解的路线，但我不确定这是否是这样做的方法。任何正确方向的指导表示赞赏。

细节：

  • 这棵树不是二叉树。这是一个无向图，有 n-1 条边，n 个顶点，没有环。只是你的普通树
  • 这棵树的顶点编号从 1 到 n。有 n-1 条无向边连接 n-1 对这些顶点
  • 'a' 和 'b' 是树中从 1 到 n 编号的任意 2 个顶点。我们要在从“a”到“b”的路径中找到第“k”个节点。保证 'k' 的值 <= 从 'a' 到 'b' 的路径中的节点数

BFS 应用于每个查询（从“a”到“b”的第 k 个节点）不是一个选项，因为查询的数量很大。

4

1 回答 1

2

做最低共同祖先，并为每个节点保留它的深度（到根的距离）。

接下来确定第 k 个节点是在 a 到 lca 还是 lca 到 b 部分。深度的差异是它们之间的节点数，因此如果depth[a] - depth[lca] > k节点位于 lca-b 部分。

如果节点在 a 到 lca 部分，只需找到 a 的第 k 个祖先。使用您预先计算的 LCA 数据应该是 log(N)。

如果节点在 b 到 lca 部分，那么您可以计算 k' ，这是第 k 个节点到 b ( k' = 1 + depth[a] + depth[b] - 2*depth[lca] - k)) 的距离，然后得到 b 的 k' 祖先（同样容易使用 LCA 数据）。

总体而言，所有查找都是 logN，其他步骤是恒定的，因此您每次查询都执行 O(LogN)。

于 2016-01-25T15:45:09.450 回答