C++ O(1) space inorder traversal easy understanding solution


  • 0

    The main idea is to traverse through the tree in order. At every node, take down the frequency of current node's value and update the max frequency if current frequency is larger than or equal to max frequency.

    class Solution {
    public:
        vector<int> findMode(TreeNode* root) {
            vector<int> mode;  
            int maxfreq = 0, curfreq = 0, curval = 0;
            inorder_traverse(root, mode, maxfreq, curfreq, curval);
            return mode;
        }
        
        void inorder_traverse(TreeNode* root, vector<int>& mode, int& maxfreq, int& curfreq, int& curval){
            if(!root) return;
            inorder_traverse(root->left, mode, maxfreq, curfreq, curval);
            
            if(root->val == curval){
                curfreq++;
                if(curfreq == maxfreq)
                    mode.push_back(curval);
                else if(curfreq > maxfreq){
                    maxfreq = curfreq;
                    mode.clear();
                    mode.push_back(curval);
                }
            }
            else{
                curfreq = 1;
                curval = root->val;
                if(curfreq == maxfreq)
                    mode.push_back(curval);
                else if(curfreq > maxfreq){
                    maxfreq = curfreq;
                    mode.clear();
                    mode.push_back(curval);
                }            
            }
            
            inorder_traverse(root->right, mode, maxfreq, curfreq, curval);
            return;
        }
    };
    

Log in to reply
 

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