【LeetCode-简单题】501. 二叉搜索树中的众数

文章目录

    • 题目
    • 方法一:暴力哈希
    • 方法二:利用二叉搜索树的特性(递归+双指针)

题目

在这里插入图片描述

方法一:暴力哈希

这是针对于普通二叉树的解法 统计number出现次数 然后将次数最大的众数集 取出来

 Map<Integer , Integer > map = new HashMap<>();PriorityQueue<int[]> priori = new PriorityQueue<>((a,b)->b[1]-a[1]);//优先队列  按数组第二个元素从大到小排List<Integer> list = new ArrayList<>();public int[] findMode(TreeNode root) {dfs(root);for(Map.Entry<Integer, Integer>  num : map.entrySet()) priori.offer(new int[]{num.getKey(),num.getValue()});int max = priori.peek()[1];int size =priori.size();for(int i = 0 ; i<size ; i++){int [] a1 = priori.poll();if(max == a1[1]) list.add(a1[0]);} return list.stream().mapToInt(Integer::intValue).toArray(); }public void dfs(TreeNode root){if(root == null) return;map.put(root.val,map.getOrDefault(root.val, 0)+1);dfs(root.left);dfs(root.right);}

方法二:利用二叉搜索树的特性(递归+双指针)

关键在于本层逻辑的处理

维护一个最大频率maxcount、单数字统计频率count、当前节点root的前一个节点 pre、

在这里插入图片描述

class Solution {List<Integer> list = new ArrayList<>();TreeNode pre = null;// 记录前一个节点int maxcount = 0; // 最大频率int count = 0;// 统计频率public int[] findMode(TreeNode root) {dfs(root);return list.stream().mapToInt(Integer::intValue).toArray();}public void dfs(TreeNode root){if(root == null) return;dfs(root.left);if(pre == null) count = 1;// 处理第一个节点else if(root.val == pre.val) count++;// 与前一个节点数值相同else count = 1;// 与前一个节点数值不同pre = root;if(count == maxcount) list.add(root.val);// 如果和最大值相同,放进result中else if(count>maxcount){// 如果计数大于最大值频率maxcount = count;// 更新最大频率list.clear(); // 很关键的一步,不要忘记清空result,之前result里的元素都失效了list.add(root.val);//再把此时的root放进result中}dfs(root.right);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/141201.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

体验亚马逊的 CodeWhisperer 感觉

CodeWhisperer 是亚马逊推出的辅助编程工具&#xff0c;在程序员写代码时&#xff0c;它能根据其内容生成多种代码建议。 CodeWhisperer 目前已支持近10几种语言&#xff0c;我是用 java 语言&#xff0c;用的开发工具是 idea&#xff0c;说一下我用的情况。 亚马逊云科技开发…

96.不同的二叉搜索树

​ 题目&#xff1a; 96. 不同的二叉搜索树 中等 2.4K 相关企业 给你一个整数 n &#xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种&#xff1f;返回满足题意的二叉搜索树的种数。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xf…

数据结构-----树和二叉树必知必会知识

目录 前言 思维导图 一.树 树的定义 二.二叉树 1.二叉树的定义 2.二叉树的形态&#xff08;图&#xff09; 3.二叉树的性质 三.满二叉树 1.定义 2.特点和性质 四.完全二叉树 1.定义 2.特点和性质 前言 今天开始我们就学习新的数据结构类型啦&#xff01;没错它就是…

python安全工具开发笔记(四)——python网络编程

一、C/S架构 什么是C/S架构 C : Client S : Server。客户机和服务器结构。 Server 唯一的目的就是等待Client 的请求&#xff0c;Client 连上 Server 发送必要的数据&#xff0c;然后等待Server端完成请求的反馈。 C/S网络编程 Server端进行设置&#xff0c;首先创建一个通信…

【LeetCode75】第六十三题 不同路径

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们返回地图的长和宽。问我们从地图的左上走到右下有几种方法。我们只能往下走或是往右走。 这个算是简单的二维动态规划题了。 …

RabbitMQ生产故障问题分析

1. 问题引发 由某个服务BI-collector-xx队列出现阻塞&#xff0c;影响很整个rabbitMQ集群服务不可用&#xff0c;多个应用MQ生产者服务出现假死状态&#xff0c;系统影响面较广&#xff0c;业务影响很大。当时为了应急处理&#xff0c;恢复系统可用&#xff0c;运维相对粗暴的把…

华为OD机试 - 相同数字组成图形的周长 - 矩阵(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、Java算法源码五、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#xff09;》。 刷的越多…

docker容器

虚拟化产品 1.奇居架构 2.原生架构 1.支持仿真虚拟化&#xff08;对系统硬件没有要求&#xff0c;性能最低&#xff09;vmware个人在windows支持 vmware workstationvmware fusion MAC2.全虚拟化产品&#xff0c;直接使用物理硬件、性能高 exic&#xff08;操作系统&#xff0…

CentOS 7 制作openssl 1.1.1w 版本rpm包 —— 筑梦之路

源码下载地址&#xff1a; https://www.openssl.org/source/openssl-1.1.1w.tar.gz 参考之前的文章&#xff1a; openssl 1.1.1L /1.1.1o/1.1.1t rpm包制作——筑梦之路_openssl的rpm包_筑梦之路的博客-CSDN博客 直接上spec文件&#xff1a; Name: openssl Version: 1.1…

【差旅游记】初见乌海湖

哈喽&#xff0c;大家好&#xff0c;我是雷工。 最近在乌海出差&#xff0c;有幸见到了传说中在沙漠中看海的“黄河明珠”——乌海湖。 前段时间一直有点忙&#xff0c;现在有点时间&#xff0c;趁还没忘光&#xff0c;简单整理记录下。 那是在上个月&#xff0c;2023年8月8号…

【大虾送书第十一期】适合新手自学的网络安全基础技能“蓝宝书”:《CTF那些事儿》

目录 &#x1f96e;写在前面 &#x1f96e;内容简介 &#x1f96e;读者对象 &#x1f96e;专家推荐 &#x1f96e;目录 &#x1f96e;文末福利 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;免费送书活动专栏地址 写在前面 CTF比赛是快…

Leetcode 887. 鸡蛋掉落

文章目录 题目代码&#xff08;9.25 首刷看解析&#xff09; 题目 Leetcode 887. 鸡蛋掉落 代码&#xff08;9.25 首刷看解析&#xff09; class Solution { public:unordered_map<int, int> memo;int superEggDrop(int K, int N) {return dp(K, N);}int dp(int k, int…

【从入门到起飞】JavaSE—方法引用

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【The truth that you leave】 &#x1f970;欢迎并且感谢大家指出我的问题 文章目录 &#x1f354;概述&#x1f354;注意&#x1f388;如何确定是否是…

Java实现byte数组与Hex互转

十六进制字符的输出大写字符&#xff1a;0123456789ABCDEF 十六进制字符的输出小写字符&#xff1a;0123456789abcdef下面使用十六进制大写字符。 1、方式1 public class HexStringUtils {private static final char[] HEX_CHAR_TABLE {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,…

LabVIEW在运行时调整表控件列宽

LabVIEW在运行时调整表控件列宽 如何在LabIEW中运行时调整表控件的列宽大小&#xff1f; 在VI运行时&#xff0c;有两种不同的方法可以更改表中列的宽度。首先&#xff0c;可以使用鼠标手动更改它们;其次&#xff0c;可以从框图中以编程方式更改它们。 手动更改列宽 只有在…

Feign 使用篇

Feign是一个声明式的HTTP客户端工具&#xff0c;它简化了在分布式系统中进行服务间通信的过程。开发人员可以使用Feign来定义接口&#xff0c;然后通过该接口来调用远程服务&#xff0c;就像调用本地方法一样简单。 目录 Feign的一些关键特性和概念&#xff1a;openfeign 对比 …

【高云FPGA系列教程(11):MultiButton按键驱动模块移植】

文章目录 1. MultiButton简介2. MultiButton代码获取3. MultiButton移植4. 测试与运行本文是高云FPGA系列教程的第11篇文章。 1. MultiButton简介 MultiButton, 一个小巧简单易用的事件驱动型按键驱动模块,可无限量扩展按键,按键事件的回调异步处理方式可以简化你的程序结构…

https跳过SSL认证时是不是就是不加密的,相当于http?

https跳过SSL认证时是不是就是不加密的,相当于http?&#xff0c;其实不是&#xff0c;HTTPS跳过SSL认证并不相当于HTTP&#xff0c;也不意味着没有加密。请注意以下几点&#xff1a; HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;本质上是在HTTP的基础上…

zabbix

利用一个优秀的监控软件可以: 通过一个友好的界面进行浏览整个网站所有的服务器状态 可以在 Web 前端方便的查看监控数据 可以回溯寻找事故发生时系统的问题和报警情况 zabbix 是什么&#xff1f; zabbix 是一个基于 Web 界面的提供分布式系统监视以及网络监视功能的企业级…