专栏首页Czy‘s Blog二叉搜索树中的众数

二叉搜索树中的众数

二叉搜索树中的众数

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

假定BST有如下定义:

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

示例

给定BST [1,null,2,2],返回[2]

   1
    \
     2
    /
   2

注意

提示:如果众数超过1个,不需考虑输出顺序。 进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    if(!root) return [];
    var cur = Infinity;
    var curCounter = 0;
    var maxValues = [];
    var maxValuesCounter = -Infinity;
    var dfs = (root) => {
        if(!root) return void 0;
        if(root.left) dfs(root.left);
        if(cur === root.val){
            ++curCounter;
        }else{
            cur = root.val;
            curCounter = 0;
        }
        if(curCounter >= maxValuesCounter){
            if(curCounter === maxValuesCounter) maxValues.push(root.val);
            else maxValues = [root.val];
            maxValuesCounter = curCounter;
        }
        if(root.right) dfs(root.right);
    }
    dfs(root);
    return maxValues;
};

思路

本题的题目中有一个进阶条件:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内),如果不考虑这个进阶条件的话,直接遍历一遍二叉树并且顶一个哈希表将遍历过的值以及出现的次数记录,之后再遍历一遍哈希表取出众数即可,考虑到这个进阶条件,那么就需要定义一些变量保存当前的状态,判断哪些条件符合要求,置入返回值,当对二叉搜索树进行二叉树中序遍历时,能够得到一个有序的序列,通过数列有序以及存储当前状态的变量即可达到目标,此外还需要注意的是题目要求是返回一个数组,也就说众数可能有多个。首先判断如果是空树直接返回空数组,定义当前值为Infinity无穷大,定义当前值计数器为0,最大值数组为空数组,最大值计数器为-Infinity负无穷大,之后定义深度递归遍历,首先判断节点不存在则直接返回,若左节点存在则向左递归,之后定义的处理位置即中序遍历,如果当前结点值与存储的遍历当前节点值相同则将计数器递增,否则将当前值置数为节点值,将计数器置0,如果当前计数器大于等于最大值的计数器则进入条件,如果这两个值相等,那么将该值置入最大值数组,否则将最大值数组置换为只有该值的数组,然后将最大值计数器赋值当前值计数器,之后判断右节点存在则向右递归,最终返回最大值数组即可。

每日一题

https://github.com/WindrunnerMax/EveryDay

参考

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 翻转二叉树

    本题是经典的二叉树操作的题目,直接从根节点进行递归遍历,并从叶子节点进行翻转,如果当前遍历到root,那么只需要继续交换两棵子树的位置即可完成翻转,首先判断节点...

    WindrunnerMax
  • 被围绕的区域

    给定一个二维的矩阵,包含X和O。 找到所有被X围绕的区域,并将这些区域里所有的O用X填充。 被围绕的区间不会存在于边界上,换句话说,任何边界上的O都不会被填...

    WindrunnerMax
  • 叶子相似的树

    举个例子,如上图所示,给定一颗叶值序列为(6, 7, 4, 9, 8)的树。 如果有两颗二叉树的叶值序列是相同,那么我们就认为它们是叶相似的。 如果给定的两...

    WindrunnerMax
  • 为ubuntu操作系统增加root用户

    1:当安装好虚拟机,安装好Ubuntu操作系统后,登陆的时候发现除了自己的设置的用户就是外来用户,其实Ubuntu中的root帐号默认是被禁用了的,所以登陆的时...

    别先生
  • LintCode-632. 二叉树的最大节点

    悠扬前奏
  • docker(常用软件安装)

    我们每次改动nginx配置文件,都需要进入容器内部?十分麻烦,我要是可以在容器外部提供一个映射路径,达到在容器外部修改文件名,容器内部就可以自动修改?-v 数据...

    崔笑颜
  • 如何把外网python虚拟环境迁移到内网

    外网python2.7 虚拟环境中安装了 flask 模块,期望在内网使用,如何迁移外网的虚拟环境到内网呢?

    砸漏
  • Ubuntu配置SecureCRT登录

    大牧莫邪
  • KVM实现分布式部署lamp并安装WordPress

    本实验要求使用KVM安装三台虚拟机,实现mysql,php,httpd,分布式部署,并完成lamp环境搭建WordPress

    用户4877748
  • Linux文件权限管理

    Dream城堡

扫码关注云+社区

领取腾讯云代金券