Java 求解二叉搜索树中的众数

向右看齐 2022-10-17 10:49 150阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、题解
     *  三、总结

## 一、题目 ##

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

假定 BST 有如下定义：

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

![在这里插入图片描述][20210602150408202.png]

## 二、题解 ##

该题如果不是二叉搜索树，则需要借助 map 实现，记录每个数字出现的频率然后输出频率最大的数字

如果借助二叉搜索树的特性，则可以利用中序遍历，遍历过程中，通过比较当前值和前驱是否相等，记录出现的最大频率

class Solution { 
        //记录结果值
        List<Integer> list;
        //记录前驱
        TreeNode pre = null;
        //统计当前频率
        int count;
        //记录最大频率
        int maxCount = Integer.MIN_VALUE;
    
        public int[] findMode(TreeNode root) { 
            //这个return无所谓，只是递归终止作用
            //因为list已经是全局的了
            if (root == null) { 
                return null;
            }
            //递归遍历左子树
            findMode(root.left);
            //第一节点，初始count=1
            if (pre == null) { 
                count = 1;
            } else if (root.val == pre.val) {  //与前一个节点值相同，频率加1
                count++;
            } else {  //当前值和前驱不同，频率值恢复到1
                count = 1;
            }
            //记录前驱值
            pre = root;
            //如果和最大频率值相同，则记录到列表集合中
            if (count == maxCount) { 
                list.add(root.val);
            }
            //当前频率大于最大频率，则更新集合，同时更新最大频率
            if (count > maxCount) { 
                // list = new ArrayList<>();
                list.clear();
                list.add(root.val);
                maxCount = count;
            }
            findMode(root.right);
            return listToArray(list);
        }
        //实现将列表转为数组
        public int[] listToArray(List<Integer> list) { 
            int[] arr = new int[list.size()];
            for (int i = 0; i < list.size(); i++) { 
                arr[i]=list.get(i);
            }
            return arr;
        }
    }

## 三、总结 ##

该题可以借助 Map 实现，也可以借助递归实现

递归实现，需要注意对于前驱的处理，及最大频率的更新

[20210602150408202.png]: /images/20221014/1b261b5dcd464f1dbdd7ee850f0a1be0.png