0

这个问题可能很多人都问过，但是，它有点不同。我们有一棵二叉树。给你两个节点 p & q。我们必须找到最不常见的父母。但是你没有指向根的根节点指针。为您提供了两个内置功能，它们是：

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

2) node* parentNode(node *c);-> 返回一个节点，它是当前节点的父节点。

如果节点 c 实际上是根节点，则 parentNode 函数将为您返回一个NULL值。使用这些函数，我们必须找到树的最不常见的父级。

4

2 回答 2

6

Step1：使用parentNode函数查找d1节点p到根的距离。类似地找到d2节点q到根的距离。（比如说，d2结果不大于d1）

第 2 步：将更远的节点（其 d 值更大）指针d2-d1移向根。

Step3：同时将指针移向根p，q直到它们指向同一个节点并返回该节点。

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

时间复杂度：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;
}
于 2012-11-08T06:14:10.967 回答
1

假设 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);
于 2012-11-08T06:21:58.837 回答