通过使用顶点数和边数之间的关系，在可能格式不正确的二叉树中查找循环

Question

我最近在一次采访中遇到了这个问题。最初的问题是

给定一个指向结构

的指针（结构使其可以指向二叉树或双向链表），编写一个函数，该函数返回它是指向二叉树还是 DLL。结构定义如下

struct node
    {
     /*data member*/
     node *l1;
     node *l2;
    };

我

立即深入研究了这个问题，但后来我意识到这个问题有些模棱两可。如果指针没有指向其中任何一个（即它是格式错误的 DLL 或格式错误的树），该怎么办？所以面试官告诉我，然后我必须编写函数，以便它可以返回所有三种情况。所以函数的返回值成为形式的枚举

enum StatesOfRoot 
   {
   TREE,
   DLL,
   INVALID_DATA_STRUCTURE,  /* case of malformed dll or malformed tree */
   EITHER_TREE_DLL,         /* case when there is only 1 node */
   };

因此，问题简化为验证二叉树和DLL的属性，对于DLL来说，这很容易。对于二叉树，我能想到的唯一验证是，从根到节点的路径不应超过一条。（或者不应该有任何循环）所以我建议我们进行深度优先搜索，并使用HashMap（面试官直接拒绝）或使用BST维护一组访问的节点（我想使用std：：set，但面试官突然弹出另一个限制，我不能使用STL）。他拒绝了这个想法，说我不允许使用任何其他数据结构。然后我提出了一个修改版的龟兔问题（将二叉树的每个分支视为一个单独的链接列表），他说这行不通。在那之后，我继续提出了更多有点丑陋的解决方案（涉及删除节点，维护树的副本等）

问题的核心

然后面试官提出了他的解决方案。 他说我们可以计算顶点的数量和边的数量，并断言顶点数=边数+1（二叉树必须持有的属性）。让我感到困惑的是我们如何计算顶点的数量（不使用任何额外的数据结构）？他说，这可以通过简单地执行任何遍历（预序，后序，按顺序）来完成。我反问道，如果我们没有跟踪访问过的节点，如果树中有循环，我们将如何防止无限循环。他说这是可能的，但没有告诉如何。我严重怀疑他的做法。谁能提供一些关于他提出的解决方案是否正确的见解？如果是，您将如何显式维护不同顶点的计数？请注意，您传递的内容只是一个指针，您没有其他信息。

PS：后来我收到通知，说我进入下一轮，甚至没有回答面试官的最终解决方案。应该是诡计吗？

编辑 ：

只是为了澄清一下，如果我们假设第 3 种情况不存在（也就是说我们保证它是一个 dll 或二叉树），那么问题就非常微不足道了。它是第三个案例的树部分，让我发疯。请在回答时注意这一点。

Answer 1

你对

他的解决方案持怀疑态度是对的。

双向链表是最简单的。DLL 强制执行不变量：

1. 除了空节点之外，节点的左节点的右节点是其自身。
2. 除空节点外，节点的右节点的左节点是其自身。
3. 非循环 DLL 最终将达到空值，因为您继续向左跟随。
4. 非循环 DLL 最终将达到 null，因为您一直遵循右侧。
5. 循环 DLL 最终将到达起始节点，因为您继续向左跟随。

前面的内容很容易检查，只需一个额外的临时变量，并遍历 DLL。

（注意：检查 3 和 4 或 5 可能需要很长时间。

二叉树是很难的。 BT 强制执行不变量：

1. "无循环"可以通过以下任何一项显示：
   • 演示没有两个节点指向同一节点，也没有节点指向根。
   • 演示从根开始的所有路径最终都以叶子结束。
   • 证明所有引用的节点都是不同的。
2. "无合并"可以通过以下任何一项显示：
   • 演示没有两个节点指向同一节点。
   • 证明所有引用的节点都是不同的。

正如您所建议的，可以通过遍历树并标记访问的每个节点来确定这些节点，以确保没有节点被访问两次，或者存储访问的每个节点的列表（例如在哈希集或其他结构中）以快速查找节点是否不同。

您可能可以验证树中没有没有其他数据结构的循环，只需遍历树并在树中保留当前深度的值，如果您在树中比计算机中的内存更深（或访问了更多节点），您将确保有一个无限循环。

但是，这并不能帮助我们区分二进制"有向无环图"（DAG）和二叉树。

但是，如果我们知道树中元素的数量，就像二叉树的库实现通常就是这种情况一样。你可以通过计算边缘的数量与先前已知的节点数量相比来检测无限循环，就像面试官建议的那样。

如果不提前知道这个数字，就很难知道无限大的树和大的有限树之间的区别。（除非您知道计算机的内存大小，或其他信息，例如制作树所需的时间等。

这仍然不能帮助我们检测"无合并"不变量。

我想不出任何有用的方法来确定不存在合并，如果不通过将访问的节点存储在外部数据结构中或在访问时将每个节点标记为已访问来显示没有节点被引用两次。

作为最后的手段，您可以执行以下操作：

1. 显示与计算机内存相比，基于树深度（或访问的节点数）的"无循环"。（或如下，在编辑中）
2. 通过此方法演示"无合并"。
   • 从根的左子项开始，即树的深度 1。
   • 访问深度为 1 和深度 0 的每个节点，并验证是否只有直接父节点引用所选节点。
   • 对根的右子级做同样的事情。
   • 对树中的每个节点继续此过程：
     选择一个节点，
     1. 保留对其直接父节点的引用，
     2. 访问树中更高处的每个节点，并且深度与所选节点相同，
     3. 验证在访问的节点中，只有直接父级引用所选子节点。
   • 完成此操作后，再次遍历树以验证每个节点的左右指针是否都指向同一节点。

此过程只需要一些额外的变量，但需要花费大量时间，因为您将每个节点与树中更高或相同深度的每个节点单独进行比较。

我的直觉告诉我，上面的过程将是一个 v 平方算法，而不仅仅是顺序 v。

如果你们中的任何人想到了解决此问题的另一种方法，请添加评论。

---

编辑：您可以通过简单地将搜索扩展到相同深度和更高的每个节点，而是与树中的每个节点进行比较来验证此处的"无循环"。您需要在渐进式算法中执行此操作，将每个节点与树中其上方的每个节点及其自身的深度进行比较，然后检查树中的所有节点，从比它深 1 到 5 个节点，然后从低 6-10 代，依此类推。 如果您以非渐进式方式检查，您可能会无限搜索。

Answer 2

首先，原始问题清楚地表明正确的输入是DLL或树，因此IMO没有歧义：如果输入错误，代码如何工作并不重要。

无论如何，你和你的面试官被赶到了"假设"的土地上。

但是，他所说的"不使用其他数据结构"是什么意思，因为如果不使用堆栈来记住转折点（使用递归机制或通过手动创建堆栈数据结构），您甚至无法遍历保证正确的二叉树。

所以我假设我们可以使用堆栈和递归。

一点提示：是的，我知道如果 node 结构包含树上的指针，我们可以在常量内存中做到这一点（我们可以修改指针并在最后将它们带回），但这里我们没有这些，所以我放弃了这个证明并假设这是"显而易见的"：我们必须至少能够使用递归。

好吧，我不会称以下为"简单的无序遍历"，但这里有它：

#include <stdio.h>
#include <stdbool.h>
struct node
    {
     /*data member*/
     struct node *l1;
     struct node *l2;
    };
// This one counts the nodes in a subtree of V with a depth no more than l that are equal to V0
int CountEqual(struct node* V0, struct node* V, int l)
{
    int thisOneIsEqual = 0;
    if( V == NULL ) {
        return 0;
    }
    if( l == 0 ) {
        return 0;
    }
    if( V0 == V ) {
        thisOneIsEqual = 1;
    }
    return thisOneIsEqual +
        CountEqual(V0, V->l1, l - 1) +
        CountEqual(V0, V->l2, l - 1);
}
// This one checks whether there're equal nodes in a subtree of root with a depth of L
bool Eqs(struct node* root, int L, struct node* V, int l)
{
    if( V == 0 ) {
        return false;
    }
    if( l == 0 ) {
        return false;
    }
    if( CountEqual(V, root, L) > 1 ) {
        return true;
    }
    return
        Eqs(root, L, V->l1, l - 1) ||
        Eqs(root, L, V->l2, l - 1);
}
// This checks whether the depth of the tree rooted at V is no more than l
bool HeightLessThanL(struct node* V, int l)
{
    if( V == 0 ) {
        return true;
    }
    if( l == 0 ) {
        return false;
    }
    return
        HeightLessThanL(V->l1, l - 1) &&
        HeightLessThanL(V->l2, l - 1);
}
bool isTree(struct node* root)
{
    int l = 1;
    while( 1 ) {
        if( HeightLessThanL(root, l - 1) ) {
            return true;
        }
        if( Eqs(root, l, root, l) ) {
            return false;
        }
        l++;
    }
}
// A simple test: build a correct tree, then add cycles, equal nodes etc.
#define SIZE 5
int main()
{
    struct node graph[SIZE];
    int i;
    for( i = 0; i < SIZE; ++i ) {
        graph[i].l1 = 0;
        graph[i].l2 = 0;
        if( 2 * i + 1 < SIZE ) {
            graph[i].l1 = graph + 2 * i + 1;
        }
        if( 2 * i + 2 < SIZE ) {
            graph[i].l2 = graph + 2 * i + 2;
        }
    }
    graph[1].l2 = graph + 3;
    printf( "%dn", isTree( graph ) );
    return 0;
}

这个想法是，对于某些 L，要么我们知道我们有一棵高度为 L 的树，要么在深度为 L 的子树中有两个相等的节点。

Answer 3

你必须假设一些 DLL 和树的通用接口。 抽象父级可能会定义一个虚拟的 toHead（），其中 DLL 将转到头节点，树将转到根目录并返回节点 obeject 等。 哈希表在这里结束了。 我的 C/C++ 生锈了，所以指针可能有点错误，但是，您要查找的是内存中的位置与"copyHead"的值相同，因为存储在"copyHead"中的值是头部的位置...希望这对你来说就是这样。

type *myType;
myType = &structure;
node *copyHead = myType.toHead(); // Where toHead() returns a pointer to the head.
while( copyHead != &(*myType.next()) ) {
    if(*myType.curr() == null) { return "is tree"}
}
return "is DLL";