题目
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
结点左子树中所含结点的值小于等于当前结点的值
结点右子树中所含结点的值大于等于当前结点的值
左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2],
返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解答
使用额外空间map的方法
var findMode = function(root) {
// 使用递归中序遍历
let map = new Map();
// 1. 确定递归函数以及函数参数
const traverTree = function(root) {
// 2. 确定递归终止条件
if(root === null) {
return ;
}
traverTree(root.left);
// 3. 单层递归逻辑
map.set(root.val,map.has(root.val)?map.get(root.val)+1:1);
traverTree(root.right);
}
traverTree(root);
//上面把数据都存储到map
//下面开始寻找map里面的
// 定义一个最大出现次数的初始值为root.val的出现次数
let maxCount = map.get(root.val);
// 定义一个存放结果的数组res
let res = [];
for(let [key,value] of map) {
// 如果当前值等于最大出现次数就直接在res增加该值
if(value === maxCount) {
res.push(key);
}
// 如果value的值大于原本的maxCount就清空res的所有值,因为找到了更大的
if(value>maxCount) {
res = [];
maxCount = value;
res.push(key);
}
}
return res;
};
不使用额外空间,利用二叉树性质,中序遍历(有序):
既然是搜索树,它中序遍历就是有序的。
中序遍历
const travelTree = function(cur) {
if (cur == null) return ;
travelTree(cur.left); // 左
(处理节点) // 中
travelTree(cur.right); // 右
return ;
}
作比较的话就是弄一个指针指向前一个节点,这样每次cur(当前节点)才能和pre(前一个节点)作比较。
而且初始化的时候pre = NULL,这样当pre为NULL时候,我们就知道这是比较的第一个元素。
if(pre.val === cur.val) {
count++;
}else {
count = 1;
}
pre = cur;
if(count === maxCount) {
res.push(cur.val);
}
if(count > maxCount) {
res = [];
maxCount = count;
res.push(cur.val);
}
}
完整代码
var findMode = function(root) {
// 不使用额外空间,使用中序遍历,设置出现最大次数初始值为1
let count = 0,maxCount = 1;
let pre = root,res = [];
// 1.确定递归函数及函数参数
const travelTree = function(cur) {
// 2. 确定递归终止条件
if(cur === null) {
return ;
}
travelTree(cur.left);
// 3. 单层递归逻辑
if(pre.val === cur.val) {
count++;
}else {
count = 1;
}
pre = cur;
if(count === maxCount) {
res.push(cur.val);
}
if(count > maxCount) {
res = [];
maxCount = count;
res.push(cur.val);
}
travelTree(cur.right);
}
travelTree(root);
return res;
};