binary-tree - 如何找到二叉树中所有节点对的 LCA

Question

有一些算法可以找到给定节点对的 LCA。但是是否有任何算法可以在小于 O(n^2) 的渐近时间内找到二叉树中所有节点对的 LCA？

我正在专门寻找时间跨度为 O(n log n) 的算法

Answer 1

你需要递归地考虑这个问题。考虑一棵树的根 r。r 的直接左子节点的 LCA 以及属于以 r 的直接右子节点为根的子树的所有节点。对 r 的直接右孩子和属于以 r 的直接左孩子为根的树的所有节点执行类似的操作。

因此，让我们定义一个名为 LCA 的函数，如下所示（在伪代码中）：

LCA(r)
    if r does not have both a right and left child
        return empty list.
    else
        p1 = pairs made up of left child and all the nodes rooted at right child.
        p2 = pairs made up of right child and all the nodes rooted at the left child.
        p3 = LCA(left child of r)
        p4 = LCA(right child of r)
        return p1 + p2 + p3 + p4