原题地址（简单）

方法1—哈希表+遍历

这应该是最容易想到的方法了吧。。。

遍历一遍，把各元素的值出现次数都记下来，然后找最大的那几个。

class Solution {
public:
    map<int, int> m;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        int maxVal = -1;
        for(auto it = m.begin(); it != m.end(); it++){
            if(it->second > maxVal) maxVal = it->second;
        }
        vector<int> v;
        for(auto it = m.begin(); it != m.end(); it++) {
            if(it->second == maxVal)    v.push_back(it->first);
        }
        return v;
    }
    void dfs(TreeNode* root) {
        if(!root)   return;
        m[root->val]++;
        dfs(root->left);
        dfs(root->right);
    }
};

方法2—中序遍历

假设一颗 BST 的中序遍历序列是 { -1, 0, 0, 1, 2, 2 }。我们可以发现重复出现的数字一定是一个连续出现的，例如这里的 0 和 2，它们都重复出现了，并且所有的 0 都集中在一个连续的段内，所有的 2 也集中在一个连续的段内。我们可以顺序扫描中序遍历序列，用 base 记录当前的数字，用count 记录当前数字重复的次数，用 maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用answer 数组记录出现的众数。每次扫描到一个新的元素：

• 首先更新 base和count:
  • 如果该元素和 base 相等，那么 count 自增 1
  • 否则将 base 更新为当前数字，count 复位为 1
• 然后更新maxCount：
  • 如果count=maxCount，那么说明当前的这个数字（base）出现的次数等于当前众数出现的次数，将base 加入answer 数组
  • 如果count>maxCount，那么说明当前的这个数字（base）出现的次数大于当前众数出现的次数，因此，我们需要将maxCount 更新为 count，清空 answer 数组后将base 加入answer 数组

我们可以把这个过程写成一个update 函数。这样我们在寻找出现次数最多的数字的时候就可以省去一个哈希表带来的空间消耗。

class Solution {
public:
    int base, count, maxCount;
    vector<int> ans;
    vector<int> findMode(TreeNode* root) {
        midDfs(root);
        return ans;
    }
    void midDfs(TreeNode* root){
        if(!root)   return;
        midDfs(root->left);
        update(root);
        midDfs(root->right);
    }
    void update(TreeNode* root) {
        if(root->val == base)   count++;
        else {
            base = root->val;
            count = 1;
        }
        if(count == maxCount)   ans.push_back(base);
        else if(count > maxCount) {
            maxCount = count;
            ans = vector<int> {base};
        }
    }
};

方法3—Morris遍历

Morris遍历二叉树（空间复杂度O(1)）

直接套用这篇文章中的中序遍历模板就好了

class Solution {
public:
    int base, count, maxCount;
    vector<int> answer;

    void update(int x) {
        if (x == base) {
            ++count;
        } else {
            count = 1;
            base = x;
        }
        if (count == maxCount) {
            answer.push_back(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = vector<int> {base};
        }
    }

    vector<int> findMode(TreeNode* root) {
        TreeNode *cur = root, *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 answer;
    }
};

参考官方题解