​LeetCode刷题实战501：二叉搜索树中的众数

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 二叉搜索树中的众数，我们先来看题面：

https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

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. Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than or equal to the node's key. The right subtree of a node contains only nodes with keys greater than or equal to the node's key. Both the left and right subtrees must also be binary search trees.

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值

结点右子树中所含结点的值大于等于当前结点的值

左子树和右子树都是二叉搜索树

示例

解题

https://blog.csdn.net/renweiyi1487/article/details/109489686

由于二叉树是有序的因此可以使用二叉树的中序遍历，使用一个pre指针保存当前节点的前一个节点，利用变量count进行计数，计数值如果等于最大的频率则将当前元素添加入列表当中，如果当前计数值大于最大的频率值则更新最大频率值，并且需要将列表清空，因为此时列表中的元素已经不再是众数了。

class Solution {

    // 记录前一个指针
    private TreeNode pre = null;

    // 计算出现次数
    private int count = 0;

    // 最大的出现频率
    private int maxCount = 0;

    private List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        searchBST(root);
        int[] ans = new int[list.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }

    private void searchBST(TreeNode cur) {
        if (cur == null) return;
        searchBST(cur.left);
        if (pre == null) {
            count = 1;
        } else if (pre.val == cur.val) {
            count++;
        } else if (pre.val != cur.val) {
            count = 1;
        }
        pre = cur;
        if (count == maxCount) {
            list.add(cur.val);
        } 

        if (count > maxCount) {
            maxCount = count;// 更新最大的频率
            list.clear(); // 清空列表，之前的元素失效
            list.add(cur.val);
        }
        searchBST(cur.right);
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-500题汇总，希望对你有点帮助！