函数，通过检查是否存在循环来确定二叉树的有效性

Question

我必须完成功能

bool HasLoop(Node* root)
{    
}

其通过检查二叉树是否具有任何循环来确定二叉树的有效性。

举个例子：

Valid:
X1
/  
X4   X5
    
X3   X7
Invalid:
X1
/  
X4   X5
  /  
X3   X7

我的想法是将我们遍历的每个节点标记为已访问，如果我们再次遇到已访问的节点，我们就会知道存在一个循环。但大多数例子都涉及集合，我们的课还没有复习过。如何继续？

编辑：我想到的：

struct Node
{
int data;
struct node *left; 
struct node *right;
bool visited = false;
};
bool HasLoop(Node* root)
{    
if(root==nullptr)
return;
if(root->visited)
return true;
if(!root->visited)
{
root->visited = true;
hasALoop(root->left);
hasALoop(root->right);
}
return false;

}

Answer 1

这可以通过使用visited标志属性(基本上是bool成员变量(对树进行简单遍历来完成。

首先进行遍历，清除visited标志。然后进行第二次遍历检查是否已为节点设置了visited标志。如果没有，则设置它，否则报告循环。

在伪代码中，它可能看起来像这样：

void check_loop(tree_node* const root)
{
if (root->visited)
{
// You have a loop, report it
}
else
{
root->visited = true;
// Traverse to children
if (root->left)
{
check_loop(root->left);
}
if (root->right)
{
check_loop(root->right);
}
}
}

在我上面的例子中，一旦找到循环，子树遍历就会停止。

这将检查树中的所有节点、内部节点和叶节点，还将捕获复杂的循环，而不仅仅是直接的循环。

Answer 2

您可以实现与我在最近的比赛中所做的功能类似的功能

bool vis[100000] = {false};
int flag = 0;
void HasLoop(Node* root)
{    
if(root==NULL)
return;
if(vis[root->data]==false)
vis[root->data]=true;
else
flag = 1; // This means it is already visited so set flag = 1

HasLoop(root->left);
HasLoop(root->right);
return;
}

尽管只有当树中没有重复的数据值时，此函数才有效。若您拥有它，那个么您就可以更改树的结构，使每个节点都有一个唯一的id或索引值，并可以在vis数组中进行检查。