Sharing my neat C++ in-order recursive solution


  • 0
    B

    Key to this problem is to understand in-order well and implement it carefully.
    The trick is to use a prev node for the node visited one step earlier.

    class Solution {
    public:
        void inorder(TreeNode* &cur, TreeNode* &prev, vector<int>& mode, int& maxlen, int& counter) {
            if(!cur) return;
            if(cur->left) inorder(cur->left, prev, mode, maxlen, counter);
            if(prev) {
                if(prev->val == cur->val) counter++;
                else {
                    if(maxlen < counter) {
                        while(!mode.empty()) mode.pop_back();
                        maxlen = counter;
                        mode.push_back(prev->val);
                    } else if(maxlen == counter) {
                        mode.push_back(prev->val);
                    }
                    counter = 1;
                }
            } else maxlen = 1, counter = 1;
            prev = cur;
            if(cur->right) inorder(cur->right, prev, mode, maxlen, counter);
            return;
        }
        vector<int> findMode(TreeNode* root) {
            vector<int> mode;
            if(!root) return mode;
            if(!root->left && !root->right) return vector<int>{root->val};
            TreeNode *prev = nullptr, *cur = root;
            int maxlen = 0, counter = 0;
            inorder(cur, prev, mode, maxlen, counter);
            if(counter>maxlen) {
                while(!mode.empty()) mode.pop_back();
                mode.push_back(prev->val);
            } else if(counter == maxlen) mode.push_back(prev->val);
            return mode;
        }
    };
    

Log in to reply
 

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