java - n 叉树中多个节点的最低公共(public)祖先

Question

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

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

Answer 1

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

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

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