501. 二叉搜索树中的众数

谁借莪１个温暖的怀抱￠ 2022-12-19 11:57 112阅读 0赞

# 题目描述 #

[501. 二叉搜索树中的众数][501.]

# 题目来源 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]

# 题目解析 #

我们都知道**二叉搜索树的中序遍历是有序的**，有一种方式就是把二叉搜索树中序遍历的结果存放到一个数组中，因为这个数组是升序的（虽然有重复的），我们可以遍历这个数组，这里使用几个变量

使用变量curent表示当前的值，count表示当前值的数量，maxCount表示重复数字最大的数量。list集合存放结果

1，如果节点值等于curent，count就加1，

2，如果节点不等于current，说明遇到了下一个新的值，更新current为新的值，然后让count=1；

接着比较count和maxCount的大小，

*  如果count==maxCount，就把当前节点的值加入到集合list中（遇到的值一定是个新值）。
 *  如果count>maxCount，先把list集合清空，然后再把当前节点的值加入到集合list中，最后在更新maxCount的值。

private TreeNode pre;
        private int curCount = 0;
        private int maxCount = 0;
        private ArrayList<Integer> list = new ArrayList<Integer>();
        public int[] findMode(TreeNode root) {
        
            helper(root);
            return list.stream().mapToInt(Integer::intValue).toArray() ;
        }
        
        private void helper(TreeNode root){
        
            if (root == null){
        
                return;
            }
            
            helper(root.left);
            
            if (pre == null || pre.val != root.val){
        
                curCount = 1;
            }else {
        
                curCount++;
            }
            
            if (curCount == maxCount){
        
                list.add(root.val);
            }else if (curCount > maxCount){
        
                maxCount = curCount;
                list.clear();;
                list.add(root.val);
            }
            
            pre = root;
            helper(root.right);
        }

![在这里插入图片描述][20201107170008369.png_pic_center]

[501.]: https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/6e77a48709ea47bf972b8e2d85b47fd2.png
[20201107170008369.png_pic_center]: /images/20221120/0dfee7f9e802464a9c3051670f3cb526.png