C++ O(n) time and O(1) space by inorder traversal


  • 1
    D

    The basic idea is that the inorder traversal of the BST is in ascending order. For example, the inorder traversal of the BST [2, 1, 3] is [1, 2, 3]. Then we can easily find the most frequently occurred elements by comparing the successive elements.

    class Solution {
    public:
        int maxFreq = 0, currFreq = 0, precursor = INT_MIN;
        vector<int> res;
    
        vector<int> findMode(TreeNode *root)
        {
            inorderTraversal(root);
            return res;
        }
    
        void inorderTraversal(TreeNode *root)
        {
            if (root == NULL) return; // Stop condition
            inorderTraversal(root->left); // Traverse left subtree
            if (precursor == root->val) currFreq++;
            else currFreq = 1;
            if (currFreq > maxFreq)
            {// Current node value has higher frequency than any previous visited
                res.clear();
                maxFreq = currFreq;
                res.push_back(root->val);
            }
            else if (currFreq == maxFreq)
            {// Current node value has a frequency equal to the highest of previous visited
                res.push_back(root->val);
            }
            precursor = root->val; // Update the precursor
            inorderTraversal(root->right); // Traverse right subtree
        }
    };
    

Log in to reply
 

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