Inspired by Stephan. Using Vectors in C++


  • 0
    S

    Re: Proper O(1) space
    class Solution {
    private:
    int currVal;
    int currCount = 0;
    int maxCount = 0;
    vector<int> modes;
    public:
    vector<int> findMode(TreeNode* root) {
    //Do Morris inorder Traversal
    while(root){
    if (!root->left){
    handle (root->val);
    root=root->right;
    }
    else {
    TreeNode *current=root->left;
    while (current->right!=NULL && current->right!=root)
    current=current->right;
    if (current->right==NULL){
    current->right=root;
    root=root->left;
    }
    else {
    current->right=NULL;
    handle(root->val);
    root=root->right;
    }
    }
    }
    return modes;
    }
    void handle(int val) {
    if (val != currVal) {
    currVal = val;
    currCount = 0;
    }
    currCount++;
    if (currCount > maxCount){
    modes.clear(); //Remove all the previous less occurence values
    modes.push_back(currVal);
    maxCount = currCount;
    }
    else if (currCount == maxCount)
    modes.push_back(currVal);
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.