4

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

给定一个指向结构的指针（其结构可以指向二叉树或双向链表），编写一个函数，返回它是指向二叉树还是 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（必须为二叉树保留的属性）。令我困惑的是我们如何计算顶点的数量（不使用任何额外的数据结构）？他说可以通过简单地执行任何遍历（preorder,postorder,inorder）来完成。我质疑如果树中有一个循环，我们将如何防止无限循环，因为我们没有跟踪访问过的节点。他说这是可能的，但没有告诉怎么做。我严重怀疑他的做法。谁能提供一些关于他提出的解决方案是否正确的见解？如果是，您将如何明确维护不同顶点的计数？请注意，您传递的只是一个指针，您没有其他信息。

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

编辑：

为了清楚起见，如果我们假设第三种情况不存在（即我们保证它是一个 dll 或二叉树），那么问题就很简单了。它是第三种情况的树部分让我发疯. 请在回答时注意这一点。

4

3 回答 3

1

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

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

  1. 除了空节点，一个节点的左节点的右节点就是它自己。
  2. 除了空节点，一个节点的右节点的左节点就是它自己。
  3. 当您继续向左移动时，非循环 DLL 最终将达到空值。
  4. 当您继续正确操作时，非循环 DLL 最终将达到空值。
  5. 当您继续向左移动时，循环 DLL 最终将到达起始节点。

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

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

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

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

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

如果您在树中的深度超过计算机中的内存（或访问了更多的节点），你肯定会有一个无限循环。

然而，这并不能帮助我们区分二叉“有向无环图”（DAG）和二叉树。

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

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

这仍然不能帮助我们检测“No Merges”不变量。

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

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

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

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

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

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

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

于 2012-07-11T04:46:47.583 回答
0

首先，原始问题清楚地表明正确的输入是 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( "%d\n", isTree( graph ) );
    return 0;
}

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

于 2012-07-06T05:57:49.230 回答
-1

您必须假设 DLL 和树的一些通用接口。一个抽象的父节点可能会定义一个虚拟的 toHead()，其中 DLL 将转到头节点，而树将转到根节点并返回节点对象等。哈希表在这里结束了。我的 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";
于 2012-07-06T03:51:56.360 回答