Iterative inorder traversal c++


  • 0

    During inorder traversal, count the occurence of current node. Cache the max frequency nodes so far in a vector.

        vector<int> findMode(TreeNode* root) {
            if(!root) return vector<int>();
            stack<TreeNode*> stk;
            vector<int> res;
            int maxCnt = 0, curCnt;
            pushLeft(root,stk);
            while(!stk.empty()) {
                TreeNode *n = stk.top();
                stk.pop();
                if (root && n->val == root->val) curCnt++;
                else {
                    if(root) {
                        if(curCnt > maxCnt) res.clear(); 
                        if(curCnt >= maxCnt) res.push_back(root->val);
                        maxCnt = max(maxCnt, curCnt);
                    }
                    curCnt = 1;
                    root = n;
                }
                pushLeft(n->right,stk);
            }
            if(curCnt > maxCnt) res.clear(); 
            if(curCnt >= maxCnt) res.push_back(root->val);
            return res;
        }
        void pushLeft(TreeNode *&r, stack<TreeNode*> &stk) {
             while(r) {
                stk.push(r);
                r = r->left;
            }     
        } 
    

Log in to reply
 

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