501-二叉搜索树的众数

LeetCode 501. Find Mode in Binary Search Tree

LeetCode-501

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Input: root = [1,null,2,2]
Output: [2]

method: 中序遍历

中序遍历，像查找有序数组的众数一样，记录每个数字出现的频率

记录频率的逻辑：

• 前面没有节点，频率置1
• 前面节点的值与当前节点的值相同，频率加1
• 前面节点的值与当前节点的值不同，频率置1

数组更新的逻辑：

• 如果当前频率与最大频率相等，就插入当前元素
• 如果当前频率大于最大频率，就把数组清空，放入当前元素

vector<int> res;
TreeNode *pre = nullptr;
int count, maxCount;
void traversal(TreeNode *cur) {
    if (!cur) return;
    traversal(cur->left);
    
    if (!pre) count = 1;    // 没有前节点，计数器初始化为1
    else if (pre->val == cur->val) count++; // 跟前节点一样，计数器递增
    else count = 1; // 跟前节点不同，计数器重置
    
    if (count == maxCount) res.push_back(cur->val);
    else if (count > maxCount) {
        maxCount = count;
        res.clear();     // 清空数组
        res.push_back(cur->val);
    }
    
    pre = cur;  // 注意当前节点处理完就变成了前节点
    traversal(cur->right);
}
vector<int> findMode(TreeNode* root) {
    traversal(root);
    return res;
}