C++ O(1) space, no recursion, no stack, 12ms, beats 98.5%


  • 1
    C
    vector<int> findMode(TreeNode* root) {
        vector<int> modes;
        
        int count = 0;
        int countMax = 0;
        bool hasVisited = false;
        int preVal;
    
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        while (cur) {
            if (cur->left) {
                pre = cur->left;
                while (pre->right && pre->right != cur) {
                    pre = pre->right;
                }
    
                if (pre->right) {
                    pre->right = NULL;
    
                    if (hasVisited) {
                        if (preVal == cur->val) {
                            ++count;
                        }
                        else {
                            preVal = cur->val;
                            count = 1;
                        }
    
                        if (countMax < count) {
                            countMax = count;
                            modes.clear();
                            modes.push_back(cur->val);
                        }
                        else if (countMax == count) {
                            modes.push_back(cur->val);
                        }
                    }
                    else {
                        count = countMax = 1;
                        preVal = cur->val;
                        modes.push_back(cur->val);
                        hasVisited = true;
                    }
    
                    cur = cur->right;
                }
                else {
                    pre->right = cur;
                    cur = cur->left;
                }
            }
            else {
                if (hasVisited) {
                    if (preVal == cur->val) {
                        ++count;
                    }
                    else {
                        preVal = cur->val;
                        count = 1;
                    }
    
                    if (countMax < count) {
                        countMax = count;
                        modes.clear();
                        modes.push_back(cur->val);
                    }
                    else if (countMax == count) {
                        modes.push_back(cur->val);
                    }
                }
                else {
                    count = countMax = 1;
                    preVal = cur->val;
                    modes.push_back(cur->val);
                    hasVisited = true;
                }
    
                cur = cur->right;
            }
        
        }
    
        return modes;
    }
    

  • 0

    @coolyuyuyu could you write the Interpretation of the idea?


  • 0
    C

    @yellow_guy
    This is a iterative binary tree in-order traversal. "count" is used to count how many repetition so far for the current element. "hasVisited" is used to detect if the traversal has ALREADY visited the first element of in-order sequence. This is the case we need special handling. "preVal" is the previous element of tree in-order traversal.


  • 0

    @coolyuyuyu thanks


Log in to reply
 

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