二叉搜索树 – 二叉搜索树中的众数

二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

找到数组中的众数有两种方法：

• 1 以空间换时间，使用map记录众数
• 2 以时间换空间，先对数组进行排序，然后记录众数

由于二叉树的中序遍历天然有序，此处我们使用时间换空间的方法。

经典步骤：

• 1 先处理n-1个节点
• 2 处理最后一个节点（当数组的众数都是1时，最后一个节点也是众数）

代码如下：

class Solution {
public:
    vector path;
    void traversal(TreeNode* root){
        if (root==nullptr) return ;
        traversal(root->left);
        path.push_back(root->val);
        traversal(root->right);
    }

    vector findMode(TreeNode* root) {
        if (root==nullptr) return vector();
        // 1 中序遍历找到递增序列
        traversal(root);
        // 2 找众数
        vector result;
        int curCount = 1;
        int maxCount = 1;
        // 2.1 处理前面n-1个元素
        for(int i=0; i<path.size()-1; i++){ if (path[i] == path[i+1]) curCount++; else curCount = 1; if (curCount > maxCount){
                result.clear();
                maxCount = curCount;
                result.push_back(path[i]);
            }
            else if (curCount == maxCount) result.push_back(path[i]);
        }
        // 2.2 处理最后一个元素
        if (maxCount == 1) result.push_back(path[path.size()-1]);
        return result;
    }
};