0

この質問は多くの人から聞かれたかもしれませんが、それはちょっと違います。二分木があります。そして、2つのノードpとqが与えられます。最も一般的でない親を見つける必要があります。しかし、ルートを指すルートノードポインタはありません。次の2つの組み込み関数が提供されます。

1）BOOL same(node *p, node *q);->ノードが同じである場合はtrueを返し、そうでない場合はfalseを返します。

2）node* parentNode(node *c);->現在のノードの親であるノードを返します。

ノードcが実際にルートである場合、parentNode関数はNULL値を返します。関数を使用して、ツリーの最も一般的でない親を見つける必要があります。

4

2 に答える 2

6

Step1: Using parentNode function find the distance d1 of the node p from root. similarly find distance d2 of node q from the root. (say, d2 comes out ot be greater than d1)

Step 2: Move the farther node(whose ever d-value was greater) pointer d2-d1 steps towards root.

Step3: Simultaneously move pointers p and q towards root till they point to same node and return that node.

Basically it will be like finding the merge point of two linked-lists.
Check the below link: Check if two linked lists merge. If so, where?

Time complexity: O(N)
Your code would look somewhat along the lines: 

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

Assuming 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;
}

UPDATE: A version without explicitly declared variables using recursion follows. I'm sure it can be improved and would probably never use it in production code in the current form.

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 に答える