0

我正在尝试在java中实现n叉树中多个节点的LCA。我正在使用句子的解析树，因此假设节点的子节点数 <= 6 是合理的。这里的多个节点是一个句子中的两个短语（连续单词序列）。设 k 为涉及的节点数。

一种方法是找到 k/2 对的两个节点的 LCA，我们将得到 k/2 个节点。现在在这些 k/2 节点上递归。顺序为 O(nlog k)，其中 O(n) 是线性 LCA 查找算法的复杂度。我可以更有效地做到这一点吗？

4

1 回答 1

1

我使用短语的节点是连续的这一事实解决了这个问题，即在解析树的叶节点列表中具有连续索引。

让segment1索引从start1到end1。也是如此segment2 = (start2,end2)。

和 的必需共同祖先是具有索引(start1, end1)和的(start2, end2)节点的共同祖先。min(start1,start2)max(end1,end2)

于 2012-07-15T13:59:32.790 回答