在二进制树上找到最不常见的父母

Question

这个问题可能是很多人都问的，但是有点不同。我们有一棵二进制树。您会得到两个节点P＆amp;问。我们必须找到最不常见的父母。但是您没有指向根的根节点指针。为您提供了两个内置功能：

1） BOOL same(node *p, node *q);->如果节点相同或否，则返回true。

2） node* parentNode(node *c);->返回当前节点的母体的节点。

如果节点C实际是根，则parenthnode函数将带有NULL值返回您。使用这些功能，我们必须找到树的最不常见的父。

Answer 1

step1：使用parentNode功能找到来自root节点p的距离d1。同样，从根中找到节点q的距离d2。（例如，d2大于d1）

步骤2：移动更远的节点（其D值更大）指针d2-d1步骤朝着root。

step3：同时将指针p和q移动到root，直到它们指向相同的节点并返回该节点。

基本上就像找到两个链接列表的合并点一样。
检查以下链接：检查两个链接列表是否合并。如果是这样，在哪里？

时间复杂性：o（n）
您的代码看起来有些依赖：

node* LCP(node* p, node *q){
    int d1=0, d2=0;
    for(node* t= p; t; t = parentNode(p), ++d1);
    for(node* t= q; t; t = parentNode(q), ++d2);
    if(d1>d2){
        swap(d1, d2);
        swap(p, q);
    }
    for(int i=0; i<(d2-d1); ++i)
        q = parentNode(q);
    if( same(p, q)){
        return parentNode(p);
    }
    while( !same(p, q)){
        p = parentNode(p);
        q = parentNode(q);
    }
    return p;
}

Answer 2

假设C ：

node* leastCommonParent(node *p, node *q)
{
    node *pParent = parentNode(p);
    while(pParent != 0)
    {
        node *qParent = parentNode(q);
        while(qParent != 0)
        {
            if (0 == same(pParent, qParent))
                return pParent;
            qParent = parentNode(qParent);
        }
        pParent = parentNode(pParent);
    }
    return 0;
}

更新：一个没有明确声明变量使用递归的版本。我确定它可以得到改进，并且可能永远不会以当前形式使用生产代码。

node* qParent(node *p, node *q)
{
    if (p == 0 || q == 0)
        return 0;
    if (same(p, q) == 0)
        return p;
    return qParent(p, q->parent);
}
node* pParent(node *p, node *q)
{
    return qParent(p, q) ? qParent(p, q) : pParent(p->parent, q);
}
node * result = pParent(p, q);