力扣98、530、501-java刷题笔记

2024-03-13 02:44
文章标签 java 笔记 力扣 98 刷题 501 530

本文主要是介绍力扣98、530、501-java刷题笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、98. 验证二叉搜索树 - 力扣(LeetCode)

1.1题目

给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下:

  • 节点的左

    子树

    只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:root = [2,1,3]
输出:true

示例 2:

输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。

1.2思路分析 

方法一:中序遍历加数组

中序遍历二叉树(递归实现),将遍历后的结果存放到集合中,然后对集合中的元素判断大小

中序遍历二叉树(迭代实现),将遍历后的结果存放到集合中,然后对集合中的元素判断大小

方法二:递归实现

1.3代码实现

方法一:中序遍历加数组(递归)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
//  方法一定义数组,中序遍历二叉树,将遍历的结果放入到数组中,然后对数组进行比较
class Solution {List<Integer> num = new ArrayList<>();public boolean isValidBST(TreeNode root) {fun(root);for(int i = 0 ;i<num.size()-1 ;i++){if(num.get(i) >= num.get(i+1)) return false;}return true;}public void fun(TreeNode root){if (root == null) return ;if(root.left != null) isValidBST(root.left);num.add(root.val);if(root.right !=  null) isValidBST(root.right);}
}

方法一:中序遍历加数组(迭代)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
//  迭代法中序遍历
class Solution {public boolean isValidBST(TreeNode root) {if(root == null) return true;Stack<TreeNode> stack = new Stack<>();// 定义一个节点用来存储前序节点TreeNode pre = null;while(root != null || !stack.isEmpty()){while(root!= null){stack.push(root);root = root.left;}TreeNode pop = stack.pop();if(pre!= null && pop.val <= pre.val) return false;pre = pop;root = pop.right;}return true;}
}

方法二:递归实现 

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {TreeNode pre = null;public boolean isValidBST(TreeNode root) {if(root == null) return true;boolean left =  isValidBST(root.left);if(!left){return false;}if(pre != null && root.val <= pre.val) return false;pre = root;boolean right =  isValidBST(root.right);return right;}
}

二、530. 二叉搜索树的最小绝对差 - 力扣(LeetCode)

2.1题目

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数,其数值等于两值之差的绝对值。

示例 1:

输入:root = [4,2,6,1,3]
输出:1

示例 2:

输入:root = [1,0,48,null,null,12,49]
输出:1

2.2思路分析 

方法一:中序遍历加数组

方法二:双指针

2.3代码实现

方法一:中序遍历加数组

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<Integer> num = new ArrayList<>();public int getMinimumDifference(TreeNode root) {fun(root);int min = num.get(num.size()-1);for(int i = 0 ; i<num.size()-1;i++){min = Math.abs(num.get(i)-num.get(i+1)) < min? Math.abs(num.get(i)-num.get(i+1)):min ; }return min;}public void fun(TreeNode root){if (root == null) return ;if(root.left != null) getMinimumDifference(root.left);num.add(root.val);if(root.right !=  null) getMinimumDifference(root.right);}
}

方法二:双指针 

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int min = Integer.MAX_VALUE;TreeNode pre = null;public int getMinimumDifference(TreeNode root) {if(root == null) return 0;fun(root);return min;}public void fun(TreeNode root){if(root ==  null) return ;getMinimumDifference(root.left);if(pre != null){min = Math.min(Math.abs(pre.val - root.val),min);}pre = root;getMinimumDifference(root.right);}
}

三、501. 二叉搜索树中的众数 - 力扣(LeetCode) 

3.1题目

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

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

示例 1:

输入:root = [1,null,2,2]
输出:[2]

示例 2:

输入:root = [0]
输出:[0]

3.2思路分析

代码随想录 (programmercarl.com)

3.3代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 定义结果数组ArrayList<Integer> resList = new ArrayList<>();// 定义统计次数int count = 0;// 定义最大出现次数int maxCount = 0;// 定义前序指针TreeNode pre = null;public int[] findMode(TreeNode root) {fun(root);int [] result = new int[resList.size()];for(int i = 0 ; i< resList.size();i++){result[i] = resList.get(i);}return result;}public void fun(TreeNode root){if (root == null) return ;fun(root.left);if(pre == null || pre.val != root.val) count=1;else if(pre.val == root.val) count++;if(count > maxCount){maxCount = count;resList.clear();resList.add(root.val);}else if(count == maxCount){resList.add(root.val);}pre = root;fun(root.right);}
}

这篇关于力扣98、530、501-java刷题笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis