当前位置：首页 > article >正文

LeetCode 501.二叉搜索树中的众数

article 2025/2/22 13:01:49

题目描述

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

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

假定 BST 满足如下定义：

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

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

提示：

树中节点的数目在范围 [1, 10^4] 内
-10^5 <= Node.val <= 10^5

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

思路

使用双指针遍历二叉树搜索树，统计元素出现频率，如果频率count等于maxCount（最大频率），把这个元素加入到结果集中；如果频率count大于maxCount，不仅要更新maxCount，而且要清空结果集。

代码

C++版：

/**
 * 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:
    // 递归法，中序遍历
    int maxCount = 0; // 最大频率
    int count = 0; // 统计频率
    TreeNode* pre = NULL;
    vector<int> result;
    void traversal(TreeNode * cur){
        if(cur==NULL) return;
        traversal(cur->left); // 左
        
        if(pre==NULL) count+=1;
        else if(pre->val==cur->val){ // 与前一个节点数值相同
            count++;
        }
        else{ // 与前一个节点数值不同
            count=1;
        }
        if(count>maxCount){ // 如果计数大于最大值频率
            maxCount=count; // 更新最大频率
            result.clear(); // 不要忘记清空result，之前result里的元素都失效了
            result.push_back(cur->val);
        }
        else if(count==maxCount){ // 如果和最大值相同，放进result中
            result.push_back(cur->val);
        }
        pre=cur; // 更新上一个节点

        traversal(cur->right); // 右
        return ;
    }
    vector<int> findMode(TreeNode* root) {
        traversal(root);
        return result;
    }
};

Python版：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.maxCount = 0  # 最大频率
        self.count = 0  # 统计频率
        self.pre = None
        self.result = []
    def searchBST(self, cur):
        if cur is None:
            return

        self.searchBST(cur.left)  # 左
        # 中
        if self.pre is None:  # 第一个节点
            self.count = 1
        elif self.pre.val == cur.val:  # 与前一个节点数值相同
            self.count += 1
        else:  # 与前一个节点数值不同
            self.count = 1
        self.pre = cur  # 更新上一个节点

        if self.count == self.maxCount:  # 如果与最大值频率相同，放进result中
            self.result.append(cur.val)

        if self.count > self.maxCount:  # 如果计数大于最大值频率
            self.maxCount = self.count  # 更新最大频率
            self.result = [cur.val]  # 不要忘记清空result，之前result里的元素都失效了

        self.searchBST(cur.right)  # 右
        return
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.searchBST(root)
        return self.result