algorithm - 从邻接表中找到两个节点的最低共同祖先

Question

如果我知道树中存在的每个节点的邻接列表，那么如何找出该树中存在的任何两个节点的最低共同祖先？

实际上我想找出任何两个节点之间的距离，所以我想计算 LCA。有没有办法从邻接表中计算出来？

T 中 n1 和 n2 的 LCA 是离根最远的 n1 和 n2 的共享祖先。计算最低共同祖先可能很有用，例如，作为确定树中节点对之间距离的过程的一部分：从 n1 到 n2 的距离可以计算为从根到 n1 的距离，加上距离从根到 n2，减去从根到它们最低共同祖先的距离的两倍。（来源维基）

Answer 1

我们正在处理邻接列表这一事实并没有真正改变问题。

求节点 A 和 B 的 LCA 的基本思路如下：

• 从根开始。
• 如果一个孩子的子树同时包含 A 和 B，则返回该子树的 LCA。
• 如果一个孩子包含 A 而另一个孩子包含 B。

通过返回任何情况的指标，上述检查可以相当容易地合并到单个函数中。

在无序树中，您必须在最坏的情况下探索整个树，但在二叉搜索树中，您可以通过简单地将其值与当前节点进行比较来轻松检查左子树或右子树是否可以包含节点。

但实际上你不应该使用 LCA 算法来确定距离。您应该改为修改上述内容以返回距离而不是 LCA。这样做的修改相当简单：

• 当您已经在孩子的子树中找到距离时，只需返回它。
• 如果您在单独的子树中找到了 A 和 B，则返回 A 和 B 之间的距离。
• 如果您只在孩子的子树中找到 A 或 B，只需将距离返回到 A 或 B 并带有指示符来说明您要返回的内容。

Answer 2

您可以尝试以下方法：

class Node
{
public:
    // Other stuff.
    const Node* getParent() const { return parent; }
private:
    Node* parent;
    std::vector<Node*> children;
};

const Node* getLowestCommonAncestor(const Node& lhs, const Node& rhs)
{
    for (const Node* node1 = &lhs; node1 != nullptr; node1 = node1->getParent()) {
        for (const Node* node2 = &rhs; node2 != nullptr; node2 = node2->getParent()) {
            if (node1 == node2) {
                return node1;
            }
        }
    }
    return nullptr;
}

或者，如果您没有父母：

namespace detail
{
    struct LCAFlag {
        enum { NoFound = 0, leftFound = 1, rightFound = 2 };
    };

    const Node* getLCA_Rec(const Node& root, const Node& lhs, const Node& rhs, unsigned int& flag)
    {
        if (&root == &lhs) {
            flag |= LCAFlag::leftFound;
        } else if (&root == &rhs) {
            flag |= LCAFlag::rightFound;
        }
        if (flag == (LCAFlag::leftFound | LCAFlag::rightFound)) {
            return nullptr; // both found. parent is the LCA
        }
        for (auto it = root.children.begin(); it != root.children.end(); ++it) {
            const Node* res = getLCA_Rec(**it, lhs, rhs, flag);

            if (res != nullptr) {
                return res;
            }
            if (flag == (LCAFlag::leftFound | LCAFlag::rightFound)) {
                return &root;
            }
        }
        return nullptr;
    }
}
const Node* getLCA(const Node& root, const Node& lhs, const Node& rhs)
{
    unsigned int flag = detail::LCAFlag::NoFound;
    return detail::getLCA_Rec(root, lhs, rhs, flag);
}

Answer 3

1. 保持每个节点的高度（到根的距离）。
2. 如果两个节点的高度不同，则从较深的节点向上走，直到我们在同一级别上得到节点。
3. 如果两个节点相等，那么我们就有了答案。如果没有，请再上一层并重复。

这假设您的树是有根的，并且您可以容纳一些额外的空间来存储每个节点的高度和父指针。

该算法的效率为 O(height)，因此取决于树的平衡程度。