LeetCode 501. 二叉搜索树中的众数(Java版暴打官方,还有谁(前序遍历+Mirrot+两次遍历真正的O(1)))

本文主要是介绍LeetCode 501. 二叉搜索树中的众数(Java版暴打官方,还有谁(前序遍历+Mirrot+两次遍历真正的O(1))),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树
    在这里插入图片描述
    输入:root = [1,null,2,2]
    输出:[2]
    如果树中有不止一个众数,可以按 任意顺序 返回。

第一种解法:前序遍历

利用二叉搜索树的性质,中序遍历一定是有序的,也就是相同的数一定会挨在一起;

我们可以用一个base来表示前一个数的值,max表示最多的数(也就是众数)的个数;

每次当前节点与前一个节点相同时,我们就把number+1,否则则更新base,number的值
然后再判断number是否与max相同,相同的话,则将该数添加到list结果数组中,表示该数也是一个众数;
如果number>max的话,则清空list结果数组,表示该数目前是唯一一个众数

那么如何记录前一个节点呢,我们利用中序遍历便可以记录下前一个节点,因为中序遍历是有序的。

class Solution {//保存前一个数的值int base=Integer.MIN_VALUE;//保存当前众数的个数int max=0;//保存当前这个值的个数int number=0;public int[] findMode(TreeNode root) {List<Integer> list=new ArrayList<>();dfs(root,list);//将list转换为int数组return list.stream().mapToInt(Integer::intValue).toArray();}//这里采用中序遍历,这样的话base每次就是它的前一个节点private void dfs(TreeNode root, List<Integer> list) {if (root==null) return;dfs(root.left,list);if(root.val==base){//如果当前节点的这个数等于前一个节点的数,则number数量+1number++;}else{//如果当前节点的这个数不等于前一个节点数,则更新base为当前节点值,number为1base=root.val;number=1;}if(max==number){//如果当前节点的数量等于当前众数的个数,则添加这个节点list.add(root.val);}else if(number>max){//如果当前节点的数量大于当前众数的个数,则清空众数数组,并更新众数数组为当前节点值max=number;list.clear();list.add(root.val);}dfs(root.right,list);}
}

时间复杂度为O(n),空间复杂度为O(1)
list为临时数组,与个数无关;且栈空间不计

第二种解法:Mirror算法

不清楚Mirror算法的可以去图解Mirror算法这里先看明白

class Solution {List<Integer> list=new ArrayList<>();//保存前一个数int base;//保存前一个数的个数int preNumber;//保存当前众数的个数int maxNumber;//Mirror算法public int[] findMode(TreeNode root) {while(root!=null){if(root.left!=null){TreeNode cur=root.left;while(cur.right!=null&&cur.right!=root){cur=cur.right;}if(cur.right==null){cur.right=root;root=root.left;}if(cur.right==root){updata(root.val);cur.right=null;root=root.right;}}else{updata(root.val);root=root.right;}}return list.stream().mapToInt(Integer::intValue).toArray();}private void updata(int val) {if(val==base)preNumber++;else{base=val;preNumber=1;}if(preNumber==maxNumber)list.add(base);else if(preNumber>maxNumber){maxNumber=preNumber;list.clear();list.add(val);}}
}

时间复杂度为O(n),空间复杂度为O(1),比上一个解法少了栈空间

第三种解法:两次遍历

这种解法空间复杂度达到了真正的O(1),但是两次遍历,也就是所谓的时间换空间

其实三种方法都是一个思想,因为是二叉搜索树,所以都是利用了保存前一个节点来进行的各种操作,只不过保存前一个节点的方式不一样而已

class Solution {//保存前一个数int base;//保存前一个数的个数int preNumber;//保存当前众数的个数int maxNumber;//结果数组int[] res;//结果数组的个数int resNum=0;//当前结果数组的个数int i=0;//两次遍历算法public int[] findMode(TreeNode root) {mirror(root);base=Integer.MIN_VALUE;preNumber=0;res=new int[resNum];mirror(root);return res;}private void mirror(TreeNode root){while(root!=null){if(root.left!=null){TreeNode cur=root.left;while(cur.right!=null&&cur.right!=root){cur=cur.right;}if(cur.right==null){cur.right=root;root=root.left;}if(cur.right==root){updata(root.val);cur.right=null;root=root.right;}}else{updata(root.val);root=root.right;}}}private void updata(int val) {if(val==base)preNumber++;else{base=val;preNumber=1;}if(preNumber==maxNumber){resNum++;if(res!=null) {res[i]=val;i++;}}else if(preNumber>maxNumber){resNum=1;maxNumber=preNumber;}}
}

时间复杂度O(n),遍历了两次树
空间复杂度O(1),真正的1,只有结果数组占空间了,其他都是常量空间,暴打其他栈空间的
image.png

这篇关于LeetCode 501. 二叉搜索树中的众数(Java版暴打官方,还有谁(前序遍历+Mirrot+两次遍历真正的O(1)))的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/592352

相关文章

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

Java springBoot初步使用websocket的代码示例

《JavaspringBoot初步使用websocket的代码示例》:本文主要介绍JavaspringBoot初步使用websocket的相关资料,WebSocket是一种实现实时双向通信的协... 目录一、什么是websocket二、依赖坐标地址1.springBoot父级依赖2.springBoot依赖

如何用java对接微信小程序下单后的发货接口

《如何用java对接微信小程序下单后的发货接口》:本文主要介绍在微信小程序后台实现发货通知的步骤,包括获取Access_token、使用RestTemplate调用发货接口、处理AccessTok... 目录配置参数 调用代码获取Access_token调用发货的接口类注意点总结配置参数 首先需要获取Ac

Java逻辑运算符之&&、|| 与&、 |的区别及应用

《Java逻辑运算符之&&、||与&、|的区别及应用》:本文主要介绍Java逻辑运算符之&&、||与&、|的区别及应用的相关资料,分别是&&、||与&、|,并探讨了它们在不同应用场景中... 目录前言一、基本概念与运算符介绍二、短路与与非短路与:&& 与 & 的区别1. &&:短路与(AND)2. &:非短

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente

什么是 Java 的 CyclicBarrier(代码示例)

《什么是Java的CyclicBarrier(代码示例)》CyclicBarrier是多线程协同的利器,适合需要多次同步的场景,本文通过代码示例讲解什么是Java的CyclicBarrier,感... 你的回答(口语化,面试场景)面试官:什么是 Java 的 CyclicBarrier?你:好的,我来举个例