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;} };
- 定义三个全局变量
pre、count和maxCount，分别用于记录前一个节点、当前节点值的计数和最大计数。- 定义一个全局变量
result用于记录出现次数最多的值。- 定义一个辅助函数
traversal，它接受当前节点作为参数。- 如果当前节点为空，则返回。
- 递归地遍历左子树。
- 处理当前节点：
- 如果
pre为空，说明是第一个节点，计数设为1。- 如果当前节点值与
pre节点值相等，计数加1。- 如果当前节点值与
pre节点值不等，重新计数。- 更新
pre为当前节点。- 如果当前计数等于最大计数，加入结果向量。
- 如果当前计数大于最大计数，更新最大计数并清空结果向量，然后加入当前节点的值。
- 递归地遍历右子树。
- 在
findMode函数中，重置计数和最大计数，清空结果向量，开始中序遍历，并返回结果向量。这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。