두 갈래 나무 중 두 노드의 가장 가까운 공공 조상을 찾다

제목: 두 갈래 나무 중 두 노드의 가장 가까운 공공 조상을 찾아 되돌려 달라고 한다.

class Node  
{  
   Node * left;  
   Node * right;  
   Node * parent;  
};  
/* p，q 。*/  
Node * NearestCommonAncestor(Node * p,Node * q); 

알고리즘 사상: 이 문제의 관건은 모든 노드에 부모 노드를 가리키는 바늘을 포함하는 데 있다. 이로써 프로그램은 간단한 알고리즘으로 실현할 수 있다.먼저 p의 부모 노드 p->parent를 제시한 다음에 q의 모든 부모 노드를 순서대로 p->parent와 비교한다. 만약에 두 노드가 같다는 것을 발견하면 이 노드는 최근의 공공 조상으로 직접 되돌려준다.만약 같은 노드를 찾지 못하면 q의 모든 부모 노드를 순서대로 p->parent->parent와 비교합니다...p->parent==root까지.

Node * NearestCommonAncestor(Node * root,Node * p,Node * q)  
{  
    Node * temp;  
         while(p!=NULL)  
    {  
        p=p->parent;  
        temp=q;  
        while(temp!=NULL)  
        {  
            if(p==temp->parent)  
                return p;  
            temp=temp->parent;  
        }  
    }  
}