二叉搜索树中最低共同祖先

Question

如果所有元素都是不同的，那么在BST中找到最近的共同祖先是很容易的。但是如果其中一些值是相同的呢?到目前为止，我们只是比较节点的数据，仅此而已，但现在我们需要检查节点的地址，而不仅仅是值吗?

Answer 1

是的，而不是使用您的key进行比较，使用(key, address of node)进行比较。这简化了处理非唯一键时的代码。

Answer 2

在没有看到使用的结构体类型的情况下，很难给出具体的信息，但是您可以尝试下面的伪代码:

struct BST {
    struct BST* parent;
    struct BST* left;
    struct BST* right;
    void* value;
}
find_common_ancestor(struct BST* x, struct BST* y)
{
    set<struct BST*> ancestors;
    // Add all of x's ancestors to set.
    while (true) {
        ancestors.insert(x);
        if (x == NULL)
            break;
        x = x=>parent;
    }
    // Check y's ancestors against x's until a match is found.
    while (true) {
        if (ancestors.count(y) > 0)
            return y;
        y = y->parent;
    }
}

Answer 3

这里是伪代码。把它们转换成语法。

GETLeastCommonAn(BINARYTREE BT, NODE A, NODE  B)
IF Root==NIL
    return NIL
ENDIF
IF Root==A OR root==B
    return Root
ENDIF
Left = GETLCA (Root.Left, A, B)
Right = GETLCA (Root.Right, A, B)
IF Left! = NIL AND Right! = NIL
    return root
ELSEIF Left! = NIL
    Return Left
ELSE
    Return Right
ENDIF