0

重複が含まれている可能性があるが、BST の他のすべてのロジックが損なわれていない二分探索ツリーが与えられた場合、最も頻繁に発生する要素を決定します。

class TreeNode
{
public:
    TreeNode* right = NULL;
    TreeNode* left = NULL;
    int val;

    TreeNode(int value)
    {
        val = value;
    }
};

// To keep track of the frequency of the value/node
struct holder
{
public:
    TreeNode* most = NULL;
    int count = 0;
};

int frequencyOfNode(TreeNode* root, struct holder* ptr)
{
    if (root == NULL)
    {
        return 0;
    }

    int left = frequencyOfNode(root->left, ptr);
    int right = frequencyOfNode(root->right, ptr);

// need to check of left and right are nor null
    if (left != 0 && root->val == root->left->val)
    {
        return 1 + left;
    }
    else if (right != 0 && root->val == root->right->val)
    {
        return 1 + right;
    }
    else
    {
        // left has a higher frequency
        if (left >= right)
        {
            // left is bigger;
            if (left > ptr->count)
            {
                ptr->most = root->left;
                ptr->count = left;
            }
        }
        else
        {
            // right has a higher frequency
            if (right > ptr->count)
            {
                ptr->most = root->right;
                ptr->count = right;
            }
        }

        return 1;
    }
}

二分探索木のポスト オーダー トラバーサルを実行しています。ノードが連続した順序で表示される場合、私のロジックは機能しますが、ノードが連続した順序でない場合。ノードの周波数がリセットされます。

私の時間は O(n) で、スペースは O(1) です。

問題は、ノードが連続してリンクされていない場合です。

私のサンプルツリー:

int main()
{
    TreeNode *root = new TreeNode(6);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(8);
    root->right->right->right = new TreeNode(8);
    root->right->right->right->right = new TreeNode(9);
    root->right->right->right->right->left = new TreeNode(8);
    root->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->right->right = new TreeNode(5);
    root->left->right->right->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->left->right = new TreeNode(1);
    root->left->left->right->right = new TreeNode(1);
    root->left->left->right->right = new TreeNode(2);
    root->left->left->left = new TreeNode(0);

    struct holder freq;
    int ran = frequencyOfNode(root, &freq);
    std::cout << "random" << ran << std::endl;

    std::cout << "The Node: " << freq.most->val << " frequency " << freq.count
            << std::endl;

    return 0;
}

ノードが連続していない場合 (つまり、8->8->8->9->8) を考慮する方法について、私は本当に混乱しています。

4

1 に答える 1

2

ご自身でいくつかの問題を解決されているようです。とにかく、私はこれを完全に解決し、いくつかのことを変更してすべてを簡素化することにしました. O(N) 時間と O(1) 空間を使用します。

#include <iostream>
#include <limits>

class TreeNode
{
public:
    TreeNode* right;
    TreeNode* left;
    int val;

    TreeNode(int value)
    {
        val = value;
        right = left = NULL;
    }
};

// To keep track of the frequency of the value/node
struct Holder
{
public:
    int value;
    int count;

    Holder(int v=std::numeric_limits<int>::min(), int c=-1): value(v), count(c) {}
};



void dfs(TreeNode* root, int &mostFrequent, int &mostFrequentCount, int &current, int &currentCount)
{
    if(root->left) dfs(root->left, mostFrequent, mostFrequentCount, current, currentCount); //first go to smaller

    int val = root->val;

    if(val == current) currentCount++;
    else { current=val; currentCount=1; }

    if(currentCount > mostFrequentCount) 
    {
        mostFrequent=current;
        mostFrequentCount=currentCount;
    }

    if(root->right) dfs(root->right, mostFrequent, mostFrequentCount, current, currentCount); //finally go to larger
}

Holder getMostFrequent(TreeNode *root)
{
    int mostFrequent=-1,mostFrequentCount=-1, current=std::numeric_limits<int>::min(), currentCount=-1;
    if(root) dfs(root, mostFrequent, mostFrequentCount, current, currentCount);

    return Holder(mostFrequent, mostFrequentCount);
}


int main()
{
    TreeNode *root = new TreeNode(6);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(8);
    root->right->right->right = new TreeNode(8);
    root->right->right->right->right = new TreeNode(9);
    root->right->right->right->right->left = new TreeNode(8);
    root->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->right->right = new TreeNode(5);
    root->left->right->right->right = new TreeNode(5);
    root->left->left = new TreeNode(1);
    root->left->left->right = new TreeNode(1);
    root->left->left->right->right = new TreeNode(1);
    root->left->left->right->right = new TreeNode(2);
    root->left->left->left = new TreeNode(0);

    Holder h = getMostFrequent(root);

    std::cout << "most frequently encountered element: " << h.value << ", " << h.count << " times\n";


    return 0;
}

これは BST であるため、[左 -> 現在 -> 右] の順序でトラバースすると、要素が並べ替えられるという事実を利用しています。それだけです。

于 2016-07-06T00:28:15.200 に答える