Recursion Solution - O(1) Space (if recursion stack space does not count)


  • 2
    J

    Maintain max frequency, current count, and pointer to previous node.

    class Solution {
    public:
        vector<int> findMode(TreeNode* root) {
            vector<int> ans;
            if(!root) return ans;
            
            int max_freq = 0, cnt = 0;
            TreeNode *prev = NULL;
            
            helper(root, ans, max_freq, prev, cnt);
            
            if(cnt == max_freq) ans.push_back(prev->val);
            
            return ans;
        }
        
    private:
        void helper(TreeNode *root, vector<int> &ans, int &max_freq, TreeNode *&prev, int &cnt) {
            if(!root) return;
            
            helper(root->left, ans, max_freq, prev, cnt);
            
            if(prev && prev->val == root->val) {
                if(++cnt > max_freq) ans.clear(), max_freq = cnt;
            }
            else if(prev && prev->val != root->val) {
                if(cnt == max_freq) ans.push_back(prev->val);
                cnt = 1;
            }
            else max_freq = cnt = 1;
            
            prev = root;
            
            helper(root->right, ans, max_freq, prev, cnt);
        }
    

  • 0
    F

    @jtee Would you mind explain the logic a bit?


  • 0
    J

    @futurus

    Instead of using hashmap, I only keep track of the previous node to identify when the current node's value is different from previous node's value.

    When the values of both nodes are different, update max frequency if occurrence of current value is greater.

    Only push the value with an occurrence equal to max frequency. It is not needed to check if current occurrence is greater than the max frequency as the max frequency has been updated.


  • 1
    F

    Thank you for coming back.

    I think two very important points (to myself) from your solution is that tree is a BST and the traversal is in-order.


  • 0
    M

    you forgot to close the class braces. Good sol.


Log in to reply
 

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