(Moris中序遍历)501. 二叉搜索树中的众数

501. 二叉搜索树中的众数

空间复杂度遍历二叉树（没有开栈空间），因为每个节点访问次数不超过2，因此时间复杂度是

class Solution {
public:
    int cntm, cur, cnt;
    vector<int> vec;

    void update(int x) {
        if (vec.empty()) {
            cur = x, cnt = 1, cntm = max(cnt, cntm), vec.push_back(cur);
        } else {
            if (x != cur) cur = x, cnt = 1;
            else cnt++;

            if (cnt > cntm) cntm = cnt, vec = vector<int>{cur};
            else if (cnt == cntm) vec.push_back(cur);
        }
    }


    vector<int> findMode(TreeNode *root) {
        TreeNode *cur = root;
        TreeNode *pre = nullptr;
        while (cur) {
            if (!cur->left) {
                update(cur->val), cur = cur->right;
                continue;
            }
            pre = cur->left;
            while (pre->right && pre->right != cur) {
                pre = pre->right;
            }

            if (!pre->right)pre->right = cur, cur = cur->left;
            else pre->right = nullptr, update(cur->val), cur = cur->right;
        }
        return vec;
    }
};