C++ inorder traversal (recursive & morris)


  • 0
     vector<int> findMode(TreeNode* root) {
            vector<int> res;
            if (!root) return res;
            unordered_map<int, int> m;
            int maxCount = 1;
            helper(root, m, maxCount);
            for (auto it=m.begin();it!=m.end();++it){
                if (it->second==maxCount)
                    res.push_back(it->first);
            }
            return res;
        }
        
     void helper(TreeNode* root, unordered_map<int, int>& m, int& maxCount){
            if (!root) return;
            helper(root->left, m, maxCount);
            m[root->val]++;
            if (maxCount < m[root->val])
                maxCount = m[root->val];
            helper(root->right, m, maxCount);
        }

  • 0

    Here is another version, using Morris Traversal:

        vector<int> findMode(TreeNode* root) {
            vector<int> res;
            if (!root) return res;
            unordered_map<int, int> m;
            int maxCount = 1;
            TreeNode* cur = root, *pre;
            while(cur){
                if (!cur->left){
                    m[cur->val]++;
                    maxCount = max(maxCount, m[cur->val]);
                    cur = cur->right;
                }
                else {
                    pre = cur->left;
                    while(pre->right && pre->right!=cur)
                        pre = pre->right;
                    if (!pre->right){
                        pre->right = cur;
                        cur = cur->left;
                    }    
                    else {
                        pre->right = NULL;
                        m[cur->val]++;
                        maxCount = max(maxCount, m[cur->val]);
                        cur = cur->right;
                    }
                }
            }
            for (auto it=m.begin();it!=m.end();++it){
                if (it->second==maxCount)
                    res.push_back(it->first);
            }
            return res;
        }

Log in to reply
 

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