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

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(1) 空间？我很好奇，因为在链表的情况下，这可以在 O(1) 空间中完成，但我从未见过针对这种情况的相应有效算法。

Answer 1

您甚至无法在 O(1) 空间中访问真实的、诚实的、无循环树的每个节点，因此您所要求的显然是不可能的。 （沿途修改树的技巧不是 O(1) 空间）。

如果您愿意考虑基于堆栈的算法，那么可以按照弗洛伊德算法轻松修改常规树遍历。

Answer 2

如果图的两个顶点属于同一连通分量，则可以在对数空间中进行测试（Reingold, Omer (2008), “对数空间中的无向连通性”, Journal of the ACM 55 (4): Article 17, 24页，doi：10.1145/1391289.1391291）。连接分量是循环的；因此，如果您可以在图中找到属于同一连通分量的两个顶点，则图中存在循环。在首次提出该算法是否存在的问题 26 年后，Reingold 发布了该算法（请参阅 http:// en.wikipedia.org/wiki/Connected_component_%28graph_theory%29）。鉴于花了 25 年时间才找到对数空间解决方案，拥有 O(1) 空间算法听起来不太可能。请注意，从图中选取两个顶点并询问它们是否属于循环相当于询问它们是否属于连通分量。

该算法可以扩展到出度为 2 的图（OP：“树”）的对数空间解决方案，因为检查每对节点及其直接兄弟节点是否属于同一节点就足够了连接组件，并且可以使用标准递归树下降在 O(log n) 空间中枚举这些对。

Answer 3

如果假设循环指向“树”中相同深度或更小深度的节点，那么您可以使用两个堆栈进行 BFS（迭代版本），一个用于乌龟 (x1)，一个用于野兔 ( x2 速度）。在某些时候，野兔的堆栈要么是空的（没有循环），要么是乌龟堆栈的子集（找到循环）。所需时间为 O(nk)，空间为 O(lg n)，其中 n 是使用的节点数，k 是检查子集条件所需的时间，其上限为 lg(n)。请注意，关于循环的初始假设并不约束原​​始问题，因为它被假设为一棵树，但对于与先前节点形成循环的有限数量的弧；到树中更深节点的链接不会形成循环，而是会破坏树结构。

如果可以进一步假设循环指向祖先，则可以通过检查两个堆栈是否相等来更改子集条件，这会更快。

Answer 4

成功了！

• 运行时间：O(n)。我怀疑它最多会穿过边缘恒定的次数。没有正式证明。
• 空间：O(1)。只存储几个节点。不创建新的节点或边，仅重新排列它们。
• 破坏性：是的。它将树展平，每个节点都将中序后继作为其右子节点，并将 null 作为左子节点。

该算法尝试通过将当前节点的整个左子树移动到其上方，使其成为子树的最右节点，然后更新当前节点以在新发现的节点中找到进一步的左子树，从而使二叉树变平。如果我们知道当前节点的左子节点和前驱节点，我们可以通过几次操作移动整个子树，类似于将一个列表插入另一个列表。这样的移动保留了树的有序序列，并且总是使树更向右倾斜。

根据当前节点周围节点的本地配置，存在三种情况：左子节点与前驱节点相同，左子节点与前驱节点不同，或者没有左子树。第一种情况很简单。第二种情况需要找到前驱，第三种情况需要找到带有左子树的右侧节点。图形表示有助于理解它们。

在后两种情况下，我们可能会陷入循环。由于我们只遍历右孩子的列表，因此我们可以使用 Floyd 的循环检测算法来查找和报告循环。每个周期迟早都会轮换成这样的形式。

#include <cstdio>
#include <iostream>
#include <queue>

#define null NULL
#define int32 int

using namespace std;

/**
*   Binary tree node class
**/

template <class T>
class Node
{

    public:

    /*  Public Attributes   */

        Node* left;
        Node* right;
        T value;

};

/**
*   This exception is thrown when the flattener & cycle detector algorithm encounters a cycle
**/

class CycleException
{

    public:

    /*  Public Constructors */

        CycleException () {}
        virtual ~CycleException () {}

};

/**
*   Biny tree flattener and cycle detector class.
**/

template <class T>
class Flattener
{

    public:

    /*  Public Constructors */

        Flattener () :
            root (null),
            parent (null),
            current (null),
            top (null),
            bottom (null),
            turtle (null),
        {}

        virtual ~Flattener () {}

    /*  Public Methods  */

        /**
        *   This function flattens an alleged binary tree, throwing a new CycleException when encountering a cycle. Returns the root of the flattened tree.
        **/

        Node<T>* flatten (Node<T>* pRoot)
        {
            init(pRoot);
            //  Loop while there are left subtrees to process
            while( findNodeWithLeftSubtree() ){
                //  We need to find the topmost and rightmost node of the subtree
                findSubtree();
                //  Move the entire subtree above the current node
                moveSubtree();
            }
            //  There are no more left subtrees to process, we are finished, the tree does not contain cycles
            return root;
        }

    protected:

    /*  Protected Methods   */

        void init (Node<T>* pRoot)
        {
            //  Keep track of the root node so the tree is not lost
            root = pRoot;
            //  Keep track of the parent of the current node since it is needed for insertions
            parent = null;
            //  Keep track of the current node, obviously it is needed
            current = root;
        }

        bool findNodeWithLeftSubtree ()
        {
            //  Find a node with a left subtree using Floyd's cycle detection algorithm
            turtle = parent;
            while( current->left == null and current->right != null ){
                if( current == turtle ){
                    throw new CycleException();
                }
                parent = current;
                current = current->right;
                if( current->right != null ){
                    parent = current;
                    current = current->right;
                }
                if( turtle != null ){
                    turtle = turtle->right;
                }else{
                    turtle = root;
                }
            }
            return current->left != null;
        }

        void findSubtree ()
        {
            //  Find the topmost node
            top = current->left;
            //  The topmost and rightmost nodes are the same
            if( top->right == null ){
                bottom = top;
                return;
            }
            //  The rightmost node is buried in the right subtree of topmost node. Find it using Floyd's cycle detection algorithm applied to right childs.
            bottom = top->right;
            turtle = top;
            while( bottom->right != null ){
                if( bottom == turtle ){
                    throw new CycleException();
                }
                bottom = bottom->right;
                if( bottom->right != null ){
                    bottom = bottom->right;
                }
                turtle = turtle->right;
            }
        }

        void moveSubtree ()
        {
            //  Update root; if the current node is the root then the top is the new root
            if( root == current ){
                root = top;
            }
            //  Add subtree below parent
            if( parent != null ){
                parent->right = top;
            }
            //  Add current below subtree
            bottom->right = current;
            //  Remove subtree from current
            current->left = null;
            //  Update current; step up to process the top
            current = top;
        }

        Node<T>* root;
        Node<T>* parent;
        Node<T>* current;
        Node<T>* top;
        Node<T>* bottom;
        Node<T>* turtle;

    private:

        Flattener (Flattener&);
        Flattener& operator = (Flattener&);

};

template <class T>
void traverseFlat (Node<T>* current)
{
    while( current != null ){
        cout << dec << current->value << " @ 0x" << hex << reinterpret_cast<int32>(current) << endl;
        current = current->right;
    }
}

template <class T>
Node<T>* makeCompleteBinaryTree (int32 maxNodes)
{
    Node<T>* root = new Node<T>();
    queue<Node<T>*> q;
    q.push(root);
    int32 nodes = 1;
    while( nodes < maxNodes ){
        Node<T>* node = q.front();
        q.pop();
        node->left = new Node<T>();
        q.push(node->left);
        nodes++;
        if( nodes < maxNodes ){
            node->right = new Node<T>();
            q.push(node->right);
            nodes++;
        }
    }
    return root;
}

template <class T>
void inorderLabel (Node<T>* root)
{
    int32 label = 0;
    inorderLabel(root, label);
}

template <class T>
void inorderLabel (Node<T>* root, int32& label)
{
    if( root == null ){
        return;
    }
    inorderLabel(root->left, label);
    root->value = label++;
    inorderLabel(root->right, label);
}


int32 main (int32 argc, char* argv[])
{
    if(argc||argv){}

    typedef Node<int32> Node;

    //  Make binary tree and label it in-order
    Node* root = makeCompleteBinaryTree<int32>(1 << 24);
    inorderLabel(root);

    //  Try to flatten it
    try{
        Flattener<int32> F;
        root = F.flatten(root);
    }catch(CycleException*){
        cout << "Oh noes, cycle detected!" << endl;
        return 0;
    }

    //  Traverse its flattened form
//  traverseFlat(root);

}

Answer 5

这是一种在 O(n) 时间和 O(1) 空间内完成此操作的方法。它需要改变所谓的树，但可以在返回之前将其恢复到原始状态。

第 1 级

从根开始，找到右链表的末尾，断言它不包含循环。 然后，将结束节点右键链接到其自身。

这就是让它发挥作用的技巧。右链接到自身的结束节点以可逆的方式有效地将所有前面的节点标记为“已访问”，该方式仍然可以被识别为右链接表的末尾。

第 n 级

处理第 n-1 级中的节点，对于每个具有左子节点的节点：

1. 找到子节点右链表的末尾，断言它不包含循环。请注意，如果该节点之前被访问过，则断言将失败，因为右链表将以单节点循环结束。
2. 将结束节点右链接到其自身。
3. 如果当前右子节点不是第一个右子节点，则将前一个子节点的右端节点右链接到当前子节点。因此，所有左子节点的右链表将链接成以单节点循环结束的单个列表。原始子列表的起始点由第(n-1)层的左指针记住，因此原始列表很容易恢复。

当您处理没有左子级的级别时，您就完成了树并发现它是有效的。如果无循环断言在任何点失败，那么它就不是一棵树。

恢复

无论所谓的树是否有效，您都可以通过逐级处理、分解附加的左子列表并清空每个右链接末尾的自链接来将其恢复到原始状态。列表。停在您找到的第一个无效的左子节点（如果有）处。

为了在 O(1) 空间中执行此操作，您需要按自下而上的顺序处理级别。为了实现这一点，请遍历从根到最后一级起点的路径，并使用每个后继者的左链接返回到其前任者。然后您可以从最后一层开始，沿着左侧的链接向上移动。

为了在向后/向上跟踪左侧链接后修复它们，您需要知道它们是否反转了目标的右侧链接或（现已覆盖）左侧链接。只需将当前节点与目标的（保留的）右链接进行比较即可区分这些情况。

这是 Typescript 中的一个实现。

interface Node {
  left?: Node,
  right?: Node;
}

function checkTree(root: Node): boolean {
  if (!root) {
    return true;
  }

  // LEVEL 1
  if (!validateRightList(root)) {
    return false;
  }
  let levelStart = root;

  // LEVEL N
  // We'll set this to a left child if the tree is invalid
  let invalidNode: Node | undefined;
  let next = findLeftLink(levelStart);
  while (next) {
    let levelEnd = validateRightList(next.left!);
    if (!levelEnd) {
      invalidNode = next.left;
      break;
    }
    levelStart = next.left!;
    while (next.right !== next && (next = findLeftLink(next.right))) {
      const s = next.left!;
      const e = validateRightList(s);
      if (!e) {
        invalidNode = s;
        break;
      }
      // concatenate next level lists
      levelEnd.right = s;
      levelEnd = e;
    }
    next = invalidNode ? undefined : findLeftLink(levelStart);
  }

  // Validation complete. PREPARE FOR RECOVERY
  let prev: Node | undefined = undefined;
  for (let n = root; n !== levelStart;) {
    next = n.left ? n.left : n.right!;
    n.left = prev;  // note root.left == undefined now
    prev = n;
    n = next;
  }
  // remember the last overwritten left link in the recovery backtracking list
  let savedLeft = levelStart.left;
  levelStart.left = prev;
  
  // RECOVERY
  recoverRightList(levelStart);
  while (levelStart.left) {
    let nextLevel: Node | undefined = levelStart;
    // move up to prev level
    next = levelStart.left; // node with left link in prev level
    recoverRightList(next);
    levelStart.left = savedLeft; // fixed
    savedLeft = levelStart;
    levelStart = next;
    while (levelStart && levelStart.left && levelStart.left.right === levelStart) {
      // recover right link
      levelStart = levelStart.left;
      levelStart.right!.left = savedLeft;
      savedLeft = undefined;
    }
    // split up the level we just left
    next = findLeftLink(next.right);
    while (nextLevel && next) {
      const n: Node | undefined = nextLevel.right;
      if (n == next.left) {
        nextLevel.right = undefined;
        next = findLeftLink(next.right);
      }
      nextLevel = n;
    }
  }
  levelStart.left = savedLeft;

  // all done
  return !invalidNode;
}

/**
 * Find the end of the right-linked-list and link it to itself
 * @returns the end node, or undefined if there is a cycle
 */
function validateRightList(n: Node): Node | undefined {
  let slow = n;
  while (n.right?.right) {
    n = n.right.right;
    slow = slow.right!;
    if (slow == n) {
      return undefined; // found a cycle
    }
  }
  if (n.right) {
    n = n.right;
  }
  n.right = n;
  return n;
}

/**
 * Undo validateRightList and return end
 */
function recoverRightList(n: Node): Node {
  while (n.right && n.right !== n) {
    n = n.right;
  }
  n.right = undefined;
  return n;
}

/**
 * Traverse a terminated or validated right-list to find
 * a node with a left child
 */
function findLeftLink(n: Node | undefined): Node | undefined {
  if (!n) {
    return undefined;
  }
  while (!n.left && n.right && n.right !== n) {
    n = n.right!;
  }
  return n.left ? n : undefined;
}

这是一个检查图中示例的测试：

function treeToString(root: Node) : string {
  const map = new Map<Node, number>();
  const list: string[] = [];
  function f(n: Node | undefined) {
    if (!n) {
      return;
    }
    if (map.has(n)) {
      list.push(String(map.get(n)));
      return;
    }
    map.set(n, map.size);
    list.push('(');
    f(n.left);
    list.push(',');
    f(n.right);
    list.push(')');
  }
  f(root);
  return list.join('');
}

const testTree = {
  right: {
    left: {
      left: {},
      right: {}
    },
    right: {
      left: {
        left: {},
        right: {}
      },
      right: {}
    }
  }
} as Node;

console.log(`test Tree: ${treeToString(testTree)}`);
console.log(`valid: ${checkTree(testTree)}`);
console.log(`recovered: ${treeToString(testTree)}`);

testTree.right!.right!.left!.right = testTree.right!.left;

console.log(`test Tree: ${treeToString(testTree)}`);
console.log(`valid: ${checkTree(testTree)}`);
console.log(`recovered: ${treeToString(testTree)}`);

Answer 6

访问感知

您需要重新定义结构（我将把指针排除在外）：

class node {
    node left;
    node right;
    bool visited = false;
};

并使用以下递归算法（如果您的树明显重新工作以使用自定义堆栈）可以变得足够大）：

bool validate(node value)
{
   if (value.visited)
      return (value.visited = false);
   value.visited = true;
   if (value.left != null && !validate(value.left))
      return (value.visited = false);
   if (value.right != null && !validate(value.right))
      return (value.visited = false);
   value.visited = false;
   return true;
}

评论：技术上它确实有 O(n) 空间；因为结构体中有额外的字段。如果所有值都在树的一侧并且每个值都在循环中，那么最坏的情况也将是 O(n+1)。

深度感知

当插入到树中时，您可以跟踪最大深度：

struct node {
  node left;
  node right;
};
global int maximumDepth = 0;

void insert(node item) { insert(root, item, 1); }
void insert(node parent, node item, int depth)
{
    if (depth > maximumDepth)
        maximumDepth = depth;
    // Do your insertion magic, ensuring to pass in depth + 1 to any other insert() calls.
}

bool validate(node value, int depth)
{
    if (depth > maximumDepth)
        return false;
    if (value.left != null && !validate(value.left, depth + 1))
        return false;
    if (value.right != null && !validate(value.right, depth + 1))
        return false;
    return true;
}

注释： 存储空间是 O(n+1)，因为我们将深度存储在堆栈（以及最大深度）；时间仍然是O(n+1)。这对于无效的树会做得更好。

Answer 7

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

Answer 8

正如 ChingPing 所提到的，一个简单的 DFS 就可以解决问题。您需要将每个节点标记为已访问（需要进行从节点引用到整数的一些映射），如果尝试在已访问的节点上重新进入，则意味着存在循环。

不过，这在内存中是 O(n) 的。

Answer 9

乍一看，您会发现这个问题可以通过弗洛伊德算法的非确定性应用来解决。那么如果我们以分裂和分支的方式应用弗洛伊德的话会发生什么呢？

好吧，我们可以使用基本节点中的 Floyd's，然后在每个分支添加额外的 Floyd's。
因此，对于每个终端路径，我们都有一个到此结束的弗洛伊德算法实例。如果出现一个循环，则有一只乌龟，必须有一只相应的兔子在追它。
这样算法就结束了。 （作为副作用，每个终端节点只能由一对兔子/乌龟到达，因此存在 O(n) 次访问，因此时间为 O(n) 时间。（存储已分支的节点，这不会增加内存的数量级并防止循环情况下的内存溢出）
此外，这样做可以确保内存占用与终端节点的数量相同。终端节点的数量为 O(log n)，但最坏情况下为 O(n)。

TL;DR：每次您有选择时都应用弗洛伊德和分支：
时间：O(n)
空间：O(log n)

Answer 10

我不相信存在一种算法可以在小于 O(N) 空间的情况下遍历树。而且，对于（所谓的）二叉树，检测循环不需要比遍历树更多的空间/时间（以“顺序”术语）。我相信 DFS 将在 O(N) 时间内遍历一棵树，因此 O(N) 可能是这两种措施的极限。

Answer 11

好吧，经过进一步的思考，我相信我找到了一种方法，只要你

• 事先知道节点的数量
• 就可以对二叉树进行修改

基本思想是用 Morris中序树遍历，并统计访问节点的数量，无论是在访问阶段还是在单个前驱查找阶段。如果其中任何一个超过了节点数，则肯定存在循环。如果你没有循环，那么就相当于普通的莫里斯遍历，你的二叉树就会被恢复。

我不确定在不提前知道节点数量的情况下是否可能。会多考虑一下。

Answer 12

最容易实现且权衡最明确的答案可能是布隆过滤器。使用每个指针遍历整个树，检查它是否存在于当前的布隆过滤器中。

• 如果是这样，请将其添加到“可能的循环集”(PCS)，它本身就是布隆过滤器。
• 如果没有，请继续。

在上述任一情况下，将其添加到布隆过滤器中。此过程终止后，再次遍历树，根据 PCS 检查每个节点。这一次，存储通过 PCS 检查的每个节点。该集中的任何重复项都表示 DAG 或循环，否则不存在 DAG/循环/重复项。

显然，这不是 O(1) 空间，但通过适当的调整，布隆过滤器可以非常接近 O(1) 空间。这需要两次 O(n) 遍，并且最大的潜在空间消耗将来自最终检查。但是，根据您设计的布隆过滤器的质量，对于正确的二叉树来说，如果不是空集，则该集应该非常小。在不正确的二叉树的情况下，该集合可能在最坏的情况下存储所有有问题的节点。

如果病态树具有阻止遍历树终止的循环，则必须按照所选的遍历顺序运行弗洛伊德算法，以验证不存在病态循环（并且树的遍历终止。）被发现，然后将树标记为病态。请注意，我上面的措辞表明这是您事后要做的事情，但因为这是一种可能性，这意味着您必须首先运行弗洛伊德算法来验证步行终止，然后使用该算法如上所述。