C++ 0(1) space solution with detail explanation and comment, can anyone make it faster?


  • 0
    G

    The first one consumes lot of space. Nothing to comment.

    class Solution_extra_memory_version {
    public:
        vector<int> findMode(TreeNode* root) {
            vector<int> res;
            if (!root) return res;
            unordered_map<int, int> mp;
            int maxV = INT_MIN;
            dfs(root, mp, maxV);
            for (auto c: mp) if (c.second == maxV) res.push_back(c.first);
            return res;
        }
    
        void dfs(TreeNode* root, unordered_map<int, int> &mp, int &maxV) {
            if (!root) return;
            mp[root->val]++;
            maxV = max(maxV, mp[root->val]);
            dfs(root->left, mp, maxV);
            dfs(root->right, mp, maxV);
        }
    };
    

    Here is the second one

    /* idea: inorder traverse gives us sorted number

    e.g. 1 1 2 2 2 2 3 3

    If we can use two pointers to count the occurrence of every number, (if val == last: cnt++; otherwise cnt = 1)
    the problem can be solved.

    I used a stack<pair<int, int>> to remember the target result

    if a new and better set of solutions comes out, pop the old one and push new

    one trick here is to memorize the last value when we traverse the tree, I can't find a logic to express it now, instead I used a 2-len deque .

    another trick is to consider the corner case, i.e. the last node and the case when there is only one node*/

    class Solution { // my own o(1) memory solution
        void inorder(TreeNode* &root, stack<pair<int, int>> &stk, int &cnt, deque<int> &dq) {
            if (!root) return; 
    
            inorder(root->left, stk, cnt, dq);
            dq.push_back(root->val);
            if (dq.size() > 2) dq.pop_front(); // trim deque when its length goes beyong 2     
    
            if (dq.front() == root->val) cnt++;
            else {
                if (dq.front() != INT_MIN && dq.front() != root->val && (stk.empty() || cnt >= stk.top().second)) {
                    if (!stk.empty() && cnt > stk.top().second) while (!stk.empty()) stk.pop(); // when we meet better solution, clear the old one
                    stk.push(pair<int, int>(dq.front(), cnt));
                }
                cnt = 1; // put it outside the above loop
            }
    
            inorder(root->right, stk, cnt, dq);
        }
    
    public:
        vector<int> findMode(TreeNode* root) {
            int cnt = 1;
            vector<int> res;
            if (root && !root->left && !root->right) { // corner case: handle one-node example
                res.push_back(root->val);
                return res;
            }
    
            stack<pair<int, int>> stk;
            deque<int> dq;
    
            dq.push_back(INT_MIN); // insert a fake number, there should be better ways to handle this part. It has potentially bug
            inorder(root, stk, cnt, dq);
    
            if (dq.front() != INT_MIN  && (stk.empty() || cnt >= stk.top().second)) { // corner case: handle the last node
                if (!stk.empty() && cnt > stk.top().second) while (!stk.empty()) stk.pop();
                stk.push(pair<int, int>(dq.back(), cnt));
            }
    
            while (!stk.empty()) { // change result format
                res.push_back(stk.top().first);
                stk.pop();
            }
            return res;
        }
    };
    

Log in to reply
 

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