2

我有一个BST；

    8
   / \
  4  12
   \
    6
   /
   6

我有以下代码来计算重复计数，这里应该是 1（6 有重复）；

struct Node
{
    int data;
    Node *left, *right;
};


void inorder(Node *root, Node *previous, int count)
{
    if(root != NULL)
    {
        if(root != previous && root->data == previous->data)
            count++;
        previous = root;
        inorder(root->left, previous, count);
        cout<<root->data<<" ";
        inorder(root->right, previous, count);
    }
}

我必须使用恒定的额外空间来做到这一点。我知道它离我们很近，但我的想法是跟踪前一个节点并检查重复项，最后返回计数。但是在按顺序执行 BST 遍历时，我无法返回整数值。除此之外，还有更好的方法来计算 BST 中的重复项。我发起；

inorder(a, a, 0);
4

2 回答 2

1

让我们假设在您的 BST 中，副本只能在节点的左侧（它始终是同一侧，我们只需要选择约定并坚持下去）。只需在按顺序遍历中左递归时增加重复计数，并且值不会改变。确保通过引用而不是值传递计数。在开始之前将其归零。很好的面试问题，顺便说一句

于 2013-07-24T18:08:23.490 回答
1

在二叉搜索树中，根据插入的写入方式，重复项将始终位于左侧或右侧，在您的情况下看起来像左侧。因此，您只需要一个额外的变量来跟踪欺骗的计数，如果当前节点与上次访问的节点相同，则在您的函数中跟踪上次访问的节点增加计数。

这是一些代码免责声明：完全未经测试只知道它可以编译

int count_dupes(Node * root, Node * last = nullptr) {
    int is_dupe = 0;
    if (root->value == last->value) is_dupe = 1;
    return is_dupe + (root->right != nullptr? count_dupes(root->right,root):0)
        + (root->left!= nullptr? count_dupes(root->left,root):0);
}

顺便说一句，我觉得这是一个面试类型的问题，但 Thomas Matthews 是对的，你的树不应该插入重复项。

于 2013-07-24T17:48:20.207 回答