Есть Вдвойне список ссылок ИЛИ 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

Я полагаю, вы могли бы проверить, является ли список с двойной связью или нет с этим фрагментом кода:

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) сложность