二叉搜索树中的众数 Posted on 2021-06-24 00:00:00 2021-06-26 00:00:00 by Author 摘要 给一颗二叉搜索树，你能找出这棵树中所有的众数吗？？？？？？ # 二叉搜索树中的众数 1. 题目描述 - 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。 假定 BST 有如下定义： - 结点左子树中所含结点的值小于等于当前结点的值 - 结点右子树中所含结点的值大于等于当前结点的值 - 左子树和右子树都是二叉搜索树 - 提示：如果众数超过1个，不需考虑输出顺序。 2. 示例描述 - 示例一 - 输入：BST = [1,null,2,2] ``` 1 \ 2 / 2 ``` - 输出：[2] - 解释：2是这颗二叉搜索树的众数 3. 解题思路 - 又是一道二叉搜索树的题，首先对于本题，令我苦恼的是 二叉树的众数还不止一个，假如只有一个就好办，就先中序遍历一遍，然后找出其中的一个众数就可以了，但是题目说的是众数还不止一个，这就有点难，其二这是一颗二叉搜索树，遍历一遍只能找到其中一个众数，怎么能找出多个呢，我有点想不到好的解决方法，唯一的笨办法就是先中序遍历处理，然后再从遍历后的集合中找众数。 - 之后我觉得我这种方法有点笨，肯定有在中序遍历的过程中就能够处理的，只不过我木有想出来。之后想了许久(好久好久)还是木有想出来，于是就参照代码随想录公众号carl哥的文章，等我看完后，发现自己真的太菜了，还得多多练习算法。下面就讲讲我看完他讲解的这道题解法后我的个人理解。 - 首先我们知道二叉搜索树中序遍历是一个排序好的序列，并且众数个数有多个。而且二叉搜索树我们在处理的时候一般左子树是处理完了，然后再遍历右子树之前进行处理的，那么该节点右子树的节点值一定大于或者等于该节点值，也一定大于该节点左子树下的值，所以右子树中不存在与左子树相同的值，那么我们在遇到一颗节点后，众数一定在该节点的左子树或者右子树中，不可能一个数即在一个节点的左子树中，又在一棵树的右子树中，这是前提，给我彦祖与亦菲是知道的，因为这是一颗二叉搜索树。 - 接下来就是怎么处理众数的问题，首先我们晓得中序遍历的每个节点的前驱节点就是该节点的孩子节点。所以在处理众数的时候就放在遍历左节点递归方法的后面，和遍历右孩子递归方法的前面。为什么这么做尼，因为前面已经讲过了，在处理当前遍历的节点时候，左子树已经处理完成了，而且左子树的值是小于或者等于当前节点的值，那么在此时处理，该值在以后的遍历中不牵扯了，也就是该值在以后遍历中就不会出现，我们需要在该值出现的时候找到该值出现的次数。 - 那么最终的一步就是怎么在递归遍历的时候找出众数，而且是在递归遍历完成后找出多个众数尼。首先我们在遍历过程中定义一个指向该节点的前驱节点，如果前驱节点与该遍历的节点值相等，那么我们让该节点值得出现频率增加一，如果该节点得值与前驱节点值不一样，那么我们判断前驱节点得值得出现频率是否大于或者之前已经遍历过得值得最大频率，如果等于得话，就把该值 加入众数结果集的集合中，如果大于的话，去让之前的众数结果集清零，加入本次出现频率最多的值，其次就是然该节点的值的频率置一，因为他与前驱节点值不一样。这样整个处理过程就结束了，最后遍历完成之后，众数结果集中就存的是二叉搜索树的众数集合。下面是代码实现，大家可以跟着代码注释以及代码在理解一遍。 4. 代码示例 ```java //众数结果集 List<Integer> res = new ArrayList<>(); //首先定义一个正在遍历节点的值的出现频率的遍历 int count = 0; //定义一个前驱节点 TreeNode pre = null; //记录之前最多出现频率的次数 int maxCoun = 0; public void computeResult(TreeNode root) { //如果节点为空，直接返回，什么也不做 if (root == null) return; //否则遍历左子树 computeResult(root.left); //如果前驱节点为空，说明前驱第一次进入二叉树中 if (pre == null) { //那么正在遍历节点值的出现频率为1 count = 1; } //否则不是头一次出现，然后判断该节点与左孩子节点值是否相等 else if (pre.val == root.val) { //相等的话，该节点值的出现评论加一 count++; } else { //前驱节点与父节点的值不相等，那么正在遍历节点的值出现频率为1 count = 1; } //之后判断 该节点值的出现频率是否与之前最大的出现频率相等，如果相等就有多个众数， // 就把该值加入众数集合中 if (count == maxCoun) { res.add(root.val); } //如果大于之前最大的出现频率，就移除之前的众数，加入本次最大的出现频率的众数 if (count > maxCoun) { res.removeAll(res); res.add(root.val); maxCoun = count; } //记录前驱节点 pre = root; //继续遍历右子树，找众数 computeResult(root.right); return; } public int[] findMode(TreeNode root) { //先中序遍历，找众数 computeResult(root); //因为返回结果为数组，所以下面就把集合转化为数组 int result[] = new int[res.size()]; for (int i = 0; i < res.size(); i++) { result[i] = res.get(i); } //返回最终众数的数组形式 return result; } ```
{{ item.content }}
{{ child.content }}