IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【leetcode】501. 二叉搜索树中的众数 -> 正文阅读

[数据结构与算法]【leetcode】501. 二叉搜索树中的众数

🚅【leetcode】501. 二叉搜索树中的众数


在这里插入图片描述

🚀题目

leetcode原题链接

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:
结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树


示例 1:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MnLfI35B-1651205626505)(C:/Users/PencilX/AppData/Roaming/Typora/typora-user-images/image-20220429111633890.png)]
输入:root = [1,null,2,2]
输出:[2]


示例 2:
输入:root = [0]
输出:[0]


提示:
树中节点的数目在范围 [1, 104] 内
-105 <= Node.val <= 105
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)

🚀思路

在这里插入图片描述

首先注意这道题目中BST的定义和我们之前做的题目不同,否则也不可能有众数。

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

二叉搜索树是有序的,它的中序遍历序列是一个递增序列(此题中相邻元素可相等),因此这道题可以转化成在递增序列中寻找所有众数。

我们在中序遍历递归的过程中直接获得众数。基本代码如下:

function traverse(cur){
    if(!cur) return 
    traverse(cur.left)
    //处理当前节点
    traverse(cur.right)
    return
}

那么中间节点如何处理呢?

1??首先用pre记录前一个节点,这样才能比较。用count记录当前节点值出现的次数。

if(pre === null){	//遍历第一个节点
	count = 1
}else if(pre.val === cur.val){	
	count++
}else{	//不相等了,重新开始计数
	count = 1
}
pre = cur

2??使用maxCount来记录目前为止的众数出现的频率,初始化为0。

if(count > maxCount){	//当count > maxCount 更新maxCount
	maxCount = count
}

3??使用一个数组result来存放众数,什么时候放入众数?当count === maxCount的时候,说明找到了新的众数,那就把当前节点值加入数组result

if(count === maxCount){
    result.push(cur.val)
}

count > maxCount,之前找到的众数就不是众数了,清空result,并把当前节点值加入result,更新maxCount

if(count === maxCount){
    result.push(cur.val)
}else if(count > maxCount){
	result.splice(0,result.length)	//清空之前的众数
	result.push(cur.val)	//加入当前节点的值
	maxCount = count	//更新maxCount
}

💻代码

在这里插入图片描述

var findMode = function(root) {
    function traverse(cur){
        if(!cur) return 
        traverse(cur.left)
        //处理当前节点
        if(pre === null){	//遍历第一个节点
            count = 1
        }else if(pre.val === cur.val){	
            count++
        }else{	//不相等了,重新开始计数
            count = 1
        }
        pre = cur

        if(count === maxCount){
            result.push(cur.val)
        }else if(count > maxCount){
            result.splice(0,result.length)	//清空之前的众数
            result.push(cur.val)	//加入当前节点的值
            maxCount = count	//更新maxCount
        }
        traverse(cur.right)
        return
    }

    let result = []
    let maxCount = 0
    let count
    let pre = null
    traverse(root)
    return result
};

🍪总结

本题的关键是知道二叉搜索树的中序遍历数组是一个递增数组,学会利用指针记录前一个节点,利用数组存储众数,并且注意当找到频率出现频率更高的众数时要清空数组。

? 我 是 c o n e r , 关 注 我 的 专 栏 : \textcolor{green}{我是coner,关注我的专栏:} conerleetcode题解js

? 每 天 早 上 更 新 3 道 l e e t c o d e 题 目 的 j s 题 解 , 一 起 变 强 🚀 🚀 🚀 \textcolor{green}{每天早上更新3道leetcode题目的js题解,一起变强🚀🚀🚀} 3leetcodejs🚀🚀🚀

👍 点 赞 , 你 的 认 可 是 我 创 作 的 动 力 ! \textcolor{green}{点赞,你的认可是我创作的动力!}

?? 收 藏 , 你 的 青 睐 是 我 努 力 的 方 向 ! \textcolor{green}{收藏,你的青睐是我努力的方向!}

?? 评 论 , 你 的 意 见 是 我 进 步 的 财 富 ! \textcolor{green}{评论,你的意见是我进步的财富!}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-01 15:57:52  更:2022-05-01 16:01:02 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 5:22:54-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码