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 に答える