는 이중 링크 목록 또는 BST

Question

이

class Node { 
int data, 
Node* P1, 
Node* p2; 
} 

우리는 노드가 원형 이중 링크 목록 또는 이진 트리를 나타내는 경우, 결정해야 다음과 같은 구조의 노드를 감안할 때입니다. 제 생각에는 우리는 한 방향으로

node = givenNode; 
while(node->P1 != null && node->P1 != givenNode) 
{ 
    node = node->p1 
} 

if(node == givenNode) // It means Circular DLL 
else if(node == null) // It means Tree 

에 주어진 노드를 순회 시작해야 그리고이를 감지하는 O (n)의 시간이 걸릴 것이다.

이보다 나은 방법이 있는지 제안 해주십시오.

Answer 1

나는 당신이 코드 조각의 경우 doubl 링크 목록 여부를 확인할 수 있습니다 제안 :

node = givenNode; 
if(givenNode->P1 == null || givenNode->P2 == null) 
// It can not be double link list (circular) 
else if(givenNode->p1->p2 == givenNode || givenNode->p2->p1 == givenNode) 
{ 
//It is a double linked list 
} 
else 
{ 
It is not a double linked list 
} 

그리고 우리는 가정 ... O (1) 복잡성