Day52 代码随想录打卡|二叉树篇—二叉搜索树中的众数

题目（leecode T501）：

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

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

假定 BST 满足如下定义：

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

方法：本题要求二叉搜索树中的众数，我们还是要记住二叉搜索树的性质，中序遍历是一个递增有序的数组。因此本题我们可以理解为在一个递增有序的数组中求众数，这就好求很多了。因为递增有序的数组中相等的数肯定会是相邻出现的。因此我们只需要比较相邻的元素即可。同样使用递归法，分析三要素。

1：传入参数与返回值：传入的是树节点的指针，返回值为空，因为我们只需要对结果数组直接操作最后读取数组即可。

2：终止条件：终止条件是遇到空节点。

3：单层处理逻辑：每一层处理中，我们都要将当前节点值与前一个结点值做比较，如果相等就增加该值的count频率，如果某个值的频率为最大的频率，就将该值加入result数组中。因为我们是实时判断频率，因此可能会出现频率更大的值，我们只需要将该频率重新赋值为最新的最大频率，并清空结果数组将新的值加进去即可。

题解：

class Solution {
private:
    int count = 0;
    int maxCount = 0;
    TreeNode* pre = NULL;
    vector result;
    void searchBST(TreeNode* cur){
        if(cur == NULL) return;                       //终止条件
        searchBST(cur->left);                         //左
        if(pre == NULL){                              //中（单层处理）
            count = 1;
        }else if(pre->val == cur->val){
            count++;
        }else{
            count = 1;
        }
        pre = cur;
        if (count == maxCount) { // 如果和最大值相同，放进result中
            result.push_back(cur->val);}
        
        if(count > maxCount){
            maxCount = count;
            result.clear();
            result.push_back(cur->val);
        }
        searchBST(cur->right);                       //右
        return;
    }
public:
    vector findMode(TreeNode* root) {
        count = 0;
        maxCount = 0;
        pre = NULL; // 记录前一个节点
        result.clear();
        searchBST(root);
        return result;
    }
};