🚅【leetcode】501. 二叉搜索树中的众数
🚀题目
leetcode原题链接
给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。 如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义: 结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点的值 左子树和右子树都是二叉搜索树
示例 1: 输入: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){
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
}
💻代码
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
}
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,关注我的专栏:}
我是coner,关注我的专栏:leetcode题解js
?
每
天
早
上
更
新
3
道
l
e
e
t
c
o
d
e
题
目
的
j
s
题
解
,
一
起
变
强
🚀
🚀
🚀
\textcolor{green}{每天早上更新3道leetcode题目的js题解,一起变强🚀🚀🚀}
每天早上更新3道leetcode题目的js题解,一起变强🚀🚀🚀
👍
点
赞
,
你
的
认
可
是
我
创
作
的
动
力
!
\textcolor{green}{点赞,你的认可是我创作的动力!}
点赞,你的认可是我创作的动力!
??
收
藏
,
你
的
青
睐
是
我
努
力
的
方
向
!
\textcolor{green}{收藏,你的青睐是我努力的方向!}
收藏,你的青睐是我努力的方向!
??
评
论
,
你
的
意
见
是
我
进
步
的
财
富
!
\textcolor{green}{评论,你的意见是我进步的财富!}
评论,你的意见是我进步的财富!
|