力扣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的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》:本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1:添加依赖步骤 2:解析 JWT2. 使用 N

springboot项目如何开启https服务

《springboot项目如何开启https服务》:本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Java中的JSONObject详解

《Java中的JSONObject详解》:本文主要介绍Java中的JSONObject详解,需要的朋友可以参考下... Java中的jsONObject详解一、引言在Java开发中,处理JSON数据是一种常见的需求。JSONObject是处理JSON对象的一个非常有用的类,它提供了一系列的API来操作J

SpringBoot多数据源配置完整指南

《SpringBoot多数据源配置完整指南》在复杂的企业应用中,经常需要连接多个数据库,SpringBoot提供了灵活的多数据源配置方式,以下是详细的实现方案,需要的朋友可以参考下... 目录一、基础多数据源配置1. 添加依赖2. 配置多个数据源3. 配置数据源Bean二、JPA多数据源配置1. 配置主数据