algorithm - 是双向链接列表还是BST

给定具有以下结构的节点

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）时间。
请建议是否有比这更好的方法。

最佳答案

我建议你可以用这段代码检查它是否是双链接列表：

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）复杂度

关于algorithm - 是双向链接列表还是BST，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12563074/