183.二叉树：二叉搜索树中的众数（力扣）

代码解决

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* pre = nullptr; // 用于记录前一个节点
    int count = 0, maxCount = 0; // 当前节点值的计数和最大计数
    vector result; // 记录出现次数最多的值
    
    // 中序遍历函数
    void traversal(TreeNode* node)
    {
        if(node == nullptr) return; // 如果当前节点为空，则返回

        traversal(node->left); // 递归遍历左子树

        // 处理当前节点
        if(pre == nullptr) 
        {
            count = 1; // 如果前一个节点为空，说明是第一个节点，计数设为1
        }
        else if(pre->val == node->val)
        {
            count++; // 如果当前节点值与前一个节点值相等，计数加1
        }
        else
        {
            count = 1; // 如果当前节点值与前一个节点值不等，重新计数
        }
        pre = node; // 更新前一个节点为当前节点

        if(count == maxCount)
        {
            result.push_back(node->val); // 如果当前计数等于最大计数，加入结果
        }

        if(count > maxCount)
        {
            maxCount = count; // 如果当前计数大于最大计数，更新最大计数并清空结果重新加入
            result.clear();
            result.push_back(node->val);
        }

        traversal(node->right); // 递归遍历右子树
    }

    // 找到二叉搜索树中出现次数最多的值
    vector findMode(TreeNode* root) 
    {
        count = 0;
        maxCount = 0;
        pre = nullptr; // 重置前一个节点
        result.clear();
        traversal(root); // 开始中序遍历
        return result;
    }
};

1. 定义三个全局变量 pre、count 和 maxCount，分别用于记录前一个节点、当前节点值的计数和最大计数。
2. 定义一个全局变量 result 用于记录出现次数最多的值。
3. 定义一个辅助函数 traversal，它接受当前节点作为参数。
4. 如果当前节点为空，则返回。
5. 递归地遍历左子树。
6. 处理当前节点：
   • 如果 pre 为空，说明是第一个节点，计数设为1。
   • 如果当前节点值与 pre 节点值相等，计数加1。
   • 如果当前节点值与 pre 节点值不等，重新计数。
   • 更新 pre 为当前节点。
   • 如果当前计数等于最大计数，加入结果向量。
   • 如果当前计数大于最大计数，更新最大计数并清空结果向量，然后加入当前节点的值。
7. 递归地遍历右子树。
8. 在 findMode 函数中，重置计数和最大计数，清空结果向量，开始中序遍历，并返回结果向量。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。