【亡羊补牢】挑战数据结构与算法 第39期 LeetCode 501. 二叉搜索树中的众数(二叉树)
发布日期:2021-06-29 14:34:18
浏览次数:2
分类:技术文章
本文共 1577 字,大约阅读时间需要 5 分钟。
仰望星空的人,不应该被嘲笑
题目描述
给定一个有相同值的二叉搜索树(BST),找出 BST 中的所有众数(出现频率最高的元素)。
假定 BST 有如下定义:
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
例如:
给定 BST [1,null,2,2], 1 \ 2 / 2返回[2].
提示:如果众数超过1个,不需考虑输出顺序
进阶:你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-mode-in-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解题思路
由于 BST
(二叉搜索树)的特殊性,我们采用递归来中序遍历,访问的节点值是有序的。然后重复节点,用计数器进行累加即可,如果有新值出现,则更新新值,然后计数器重置为 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) { let cnt = 0; let pre = 0; let res = []; let maxCnt = 0; let handle = (cur) => { // 相同的数,累加 if(cur === pre){ cnt++; }else{ // 有新数出现,重新置计数器为1,更新新数 pre = cur; cnt = 1; } // 如果次数超过了最大值,更新当前最大值 if(cnt > maxCnt){ maxCnt = cnt; res = [cur]; // 如果有相同频率的数字出现,直接加入 }else if(cnt === maxCnt){ res.push(cur); } } // 二叉搜索树,递归中序遍历方式 let inOrder = (root) =>{ if(!root) return null; inOrder(root.left); handle(root.val); inOrder(root.right); } inOrder(root); return res;};
最后
文章产出不易,还望各位小伙伴们支持一波!
往期精选:
小伙伴们可以在Issues中提交自己的解题代码,🤝 欢迎Contributing,可打卡刷题,Give a ⭐️ if this project helped you!
,方便小伙伴阅读玩耍~
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/108785911 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月09日 21时05分10秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
力扣的删除排序数组中的重复项解法(python)
2019-04-29
力扣的移除元素 解法 Python3
2019-04-29
力扣的三数之和解法(Python3)
2019-04-29
力扣的最接近的三数之和解法(Python3)
2019-04-29
力扣的买卖股票的最佳时机 III之解法(Python3)
2019-04-29
LeetCode 合并两个有序链表 解法 (Python)
2019-04-29
力扣的删除排序链表中的重复元素解法 (Python3)
2019-04-29
力扣的环形链表解法 (Python)
2019-04-29
力扣的盛最多水的容器解法 (Python)
2019-04-29
力扣的电话号码的字母组合解法(Python)
2019-04-29
力扣的组合总和解法 (Python)
2019-04-29
力扣的两数相加解法 (Python)
2019-04-29
力扣的删除链表的倒数第N个节点解法(Python)
2019-04-29
力扣的串联所有单词的子串解法(Python)
2019-04-29
力扣的接雨水解法(Python3)
2019-04-29
HTML5 五种密码框
2019-04-29
Node.js npm uuid
2019-04-29
JavaScript 滑动验证
2019-04-29
CSS3 二级菜单
2019-04-29
CSS3 帧动画(Sprite,直译叫雪碧图)
2019-04-29