Leetcode面试经典150题-98.验证搜索二叉树

ops/2025/1/11 20:47:32/

 解法都在代码里,不懂就留言或者私信

二叉树的递归套路,练练就习惯了

/*** 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 {/**首先你应该直到什么是二叉搜索树,二叉搜索树的特征就是对于某个节点,如果左树存在则左树上最大的节点小于当前节点如果右树存在,右树上最小的节点大于当前节点那么对于二叉树的递归套路,我们需要向左右子树要三个信息:1.是不是二叉搜索树2.最小节点的值3.最大节点的值 */public boolean isValidBST(TreeNode root) {Info info = getInfo(root);return info.isBST;}public Info getInfo(TreeNode root) {/**如果是空就返回null */if(root == null) {return null;}/**最大值最小值先设置为root的值 */int minVal = root.val;int maxVal = root.val;/**目前没有发现违反二叉搜索树规则的地方,暂时认为它是 */boolean isBST = true;/**拿到左右子树的信息 */Info leftInfo = getInfo(root.left);Info rightInfo = getInfo(root.right);/**左树不为空根据左树信息加工自己的三个信息 */if(leftInfo != null) {minVal = Math.min(minVal, leftInfo.minVal);maxVal = Math.max(maxVal, leftInfo.maxVal);isBST = leftInfo.isBST && isBST && leftInfo.maxVal < root.val;}/**右树不为空根据右树的信息加工自己的三个信息 */if(rightInfo != null) {minVal = Math.min(minVal, rightInfo.minVal);maxVal = Math.max(maxVal, rightInfo.maxVal);isBST = rightInfo.isBST &&  isBST && rightInfo.minVal > root.val;}/**根据自己的三个信息构造Info并返回 */return new Info(minVal, maxVal, isBST);}static class Info {int minVal;int maxVal;boolean isBST;public Info(int minVal, int maxVal, boolean isBST) {this.minVal = minVal;this.maxVal = maxVal;this.isBST = isBST;}}
}


http://www.ppmy.cn/ops/108884.html

相关文章

如何在快节奏的IT行业中保持学习动力

在瞬息万变的IT行业&#xff0c;技术的快速更新让程序员面临持续学习的压力。新的编程语言、框架和工具层出不穷&#xff0c;迫使我们时刻保持竞争力。然而&#xff0c;长期的高强度学习和工作容易让人感到疲惫和倦怠&#xff0c;削弱对技术的热情。本文将探讨几种有效的策略&a…

代码审计总结

代码审计总结 概述 一、代码审计 1.1什么是代码审计&#xff1f; 1.2为什么要执行代码审核&#xff1f; 1.3代码审计的好处 二、代码审计流程 2.1代码检查方法 2.2代码检查项目 2.3编码规范 2.4代码检查规范 2.5缺陷检查表 2.6代码审计复查 2.7代码审计结果总结 三…

Pytorch深度学习快速入门笔记【小土堆】

目录 1 Python学习中两大重要函数 2 Python代码编辑的三种方式 3 Pytorch学习 3.1 Dataset和DataLoader 3.1.1 Dataset 3.1.2 DataLoader 3.2 TensorBoard 3.2.1 add_scalar 3.2.2 add_image 3.3 Transforms 3.3.1 ToTensor 3.3.2 Normalize 3.3.3 Resize 3.3.4 C…

数据结构 Java DS——分享部分链表题目 (2)

前言 关于JAVA的链表,笔者已经写了两篇博客来介绍了,今天给笔者们带来第三篇,也是分享了一些笔者写过的,觉得挺好的题目,链接也已经挂上了,笔者们可以去看看 入门数据结构JAVA DS——如何实现简易的单链表(用JAVA实现)-CSDN博客 数据结构 Java DS——链表部分经典题目 (1)-C…

华为 HCIP-Datacom H12-821 题库 (9)

有需要题库的可以看主页置顶 V群进行学习交流 1.以下关于 RSTP 保护功能的描述&#xff0c;错误的是哪一选项&#xff1f; A、环路保护可以部署在根端口上&#xff0c;以防网络中形成环路 B、环路保护可以部署在Alternate 端口上&#xff0c;以防网络中形成环路 C、BPDU 保…

python正则表达式

正则替换特殊字符 import re text "包含特殊字符的文本\u2002" # 替换所有非GBK字符为空格&#xff08;或其他字符&#xff09; filtered_text re.sub(r[^\x00-\x7F], , text) encoded_text filtered_text.encode(gbk)

js实现动态生成不固定数量的气泡

样式&#xff1a; 核心代码&#xff1a; 1、添加气泡的方法 addCircle() {let height 645;let width 312;let minSize 38;let maxSize 78;let newCircle {x: Math.random() * width, // 随机位置&#xff0c;留出边界y: Math.random() * height,size: (minSize Math.ra…

怎么画实体关系图E-R?用这款在线绘图工具简单又好用!

ER图(Entity-Relationship Diagram&#xff0c;即实体-关系图)是一种用于数据库设计的图形化工具&#xff0c;用于描述现实世界的概念模型。它由Peter Chen于1976年首次提出&#xff0c;现已成为数据库建模和系统分析设计中最常用的工具之一。 ER图通过图形化的方式&#xff0…