我们可以检查一个*所谓的*有向二叉树是否包含 O(1) 空间中的循环吗？

Question

这是来自 sicp，虽然有点不同：

练习 3.18。 编写一个过程来检查列表并确定它是否包含循环，即尝试通过“获取连续的 cdrs”来查找列表末尾的程序是否会进入无限循环。练习 3.13 构建了这样的列表。 练习 3.19。 使用仅占用“恒定空间量”的算法重做练习 3.18。 （这需要非常聪明的想法。）

这里我们考虑一个更通用的列表，其中 car

部分也可以列出，其中

car,cdr

表示

left,right

。我发现了一个类似的 QA

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

，但那是关于无向图的。正如

Matt Timmermans 的答案

所示，O(1) 是可能的。恕我直言，这是正确的。 但是对于上面的练习上下文，我们应该考虑有向

二叉树，因为可以通过

---

car

或cdr从父节点到子节点，但

不保证

我们也可以进入

反向

方向。 问： 那么是否可以检查一个

所谓的有向

二叉树是否包含空间复杂度为 O(1) 的循环？

在我学习了SICP以及离散数学中所学的基础数学知识之后学习CRLS时，也欢迎阅读任何参考资料。预先感谢。

你可以在 O(1) 空间中完成此操作，但我想不出一种花费少于 O(n

2

Answer 1

O(n²) 解决方案是 DFS，但由于我们需要 O(1) 空间，因此我们必须将簿记信息隐藏在树本身中。 树会发生变异，但算法完成后可以恢复到原始状态。

与大于 O(1) 的 DFS 搜索相关的状态包括：

当前打开的节点堆栈；和

已完成节点的集合。

此外，要实现DFS，您必须能够确定给定节点是否在开放堆栈上。
我们可以使用 2 个假节点作为哨兵，以一种有利于 DFS 的方式将此信息隐藏在树中。

我们持续跟踪“当前节点”，即开放堆栈的顶部。 然后，我们制作 2 个假节点用作哨兵：

T

是已完成节点的标记。 当节点
• left == T

  或左链以

  T

  结束时，节点完成。
  B
是开放节点堆栈的底部。 当节点
• left == B

  或其左链以

  B

  结束时，该节点位于开栈中。 开栈是从当前节点到
  left
的

B

链接链。 当然，这会覆盖之前在那些

left

链接中的指针，但我们可以按如下方式保留它：

对于开放堆栈上除堆栈顶部之外的每个节点，其在开放堆栈上的前任节点（具有指向它的左链接的节点）是其左子节点或右子节点。

当一个节点位于开栈而不是最顶层时，我们使用它的

right
• 指针指向“其他”子节点。如果其在开栈中的前驱是其右子节点，则其
right
• 链接指向其左子节点。当左子节点完成时，

  right

  链接只会保留左子节点，因此我们可以通过跟踪
right
• 中节点的左链来识别这种情况。 如果它以

  T

  结束，则该节点是完整的左子节点。

  开栈中最顶层的节点没有前驱，并且其左链接被覆盖以指向其父节点，因此我们需要一个单独的指针来记住其实际的左子节点。

当使用这种状态编码执行 DFS 时，我们需要能够检查发现的状态，看看它是否打开或完整。 现在只需沿着其左链查看它是否以

B

或

T

结尾即可。 每个节点都可以放入开放堆栈或通过更改其

left

链接标记为已完成。 此检查可能需要线性时间，这就是为什么当普通 DFS 为 O(n) 时，整个算法为 O(n

2

)。如果我们发现一个子节点指向开放堆栈上的节点，我们就发现了一个循环并且可以停止。 为了在这个过程之后恢复图的原始状态，我们可以撤销DFS的每一步。 每一个都是使用本地信息可逆的。