在二叉树中查找循环

Question

如何在二叉树中找到循环？我正在寻找一种解决方案,而不是将访问过的节点标记为已访问或进行地址散列.有任何想法吗？

Answer 1

正如已经提到的：树（根据定义）不包含循环（循环）。

要测试您的有向图是否包含循环（对已添加到树中的节点的引用），您可以遍历树并将每个节点添加到访问列表（如果您愿意，也可以添加到它的散列）并检查每个新节点是否它在列表中。只需谷歌搜索即可找到大量用于图表中循环检测的算法。