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<int> 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<int> 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)，因为需要存储递归调用的栈。