确定所谓的二叉树是否包含循环的高效算法？

Question

我最喜欢的面试问题之一是

在O(n)时间和O(1)空间中,确定链表是否包含循环.

这可以使用Floyd的循环寻找算法来完成.

我的问题是,在尝试检测二叉树是否包含循环时,是否可以获得如此好的时间和空间保证.也就是说,如果有人给你一个struct定义

struct node {
    node* left;
    node* right;
};

您如何有效地验证给定结构确实是二叉树,而不是DAG或包含循环的图形？

是否存在一种算法,给定二叉树的根,可以确定该树是否包含O(n)时间并且优于O(n)空间的循环？显然,这可以使用标准DFS或BFS来完成,但这需要O(n)空间.可以在O(√n)空间内完成吗？O(log n)空间？或者(O圣)在O(1)空间？我很好奇,因为在链表的情况下,这可以在O(1)空间中完成,但我从未见过相应有效的算法.

Answer 1

你甚至无法访问O(1)空间中真实的,诚实的,无循环的树的每个节点,所以你要求的东西显然是不可能的.(沿途修改树的技巧不是O(1)空间).

如果您愿意考虑基于堆栈的算法,那么可以根据Floyd的算法轻松修改常规树步行.

Answer 2

正如卡尔所说，根据定义，“树”是没有环的。但我仍然理解提出这个问题的精神。为什么需要花哨的算法来检测任何图中的循环。你可以简单地运行 BFS 或 DFS，如果你访问一个已经被访问过的节点，则意味着一个循环。这将在 O(n) 时间内运行，但空间复杂度也是 O(n)，不知道是否可以降低。