当前位置: 首页 > news >正文

98. 验证二叉搜索树

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

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

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

解题思路:
利用二叉搜索树的中序遍历是严格的升序序列,如果中序遍历过程中当前节点值小于等于上一个节点值,那么就说明不是严格递增的,自然也就不是二叉搜索树了。

注意preVal的初始值为long型的最小值,因为题目的节点值可以取到int型的最小值,如果第一个遍历的节点值刚好等于int型的最小值就会出现误判(和preVal的初始值相等了,导致返回false)。

/*** 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 {private boolean ans = true;private long preVal = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {inorder(root);return ans;}private void inorder(TreeNode root){if(root == null){return;}inorder(root.left);if(root.val <= preVal){ans = false;return;}preVal = root.val;inorder(root.right);}
}
http://www.lqws.cn/news/470233.html

相关文章:

  • Redis哨兵模式的学习(三)
  • React JSX语法
  • Hologres 使用 FDW
  • 「Linux文件及目录管理」输入输出重定向与管道
  • 网络编程及原理(六):三次握手、四次挥手
  • 什么是跨域问题?后端如何解决跨域问题?
  • 基于FPGA的白噪声信号发生器verilog实现,包含testbench和开发板硬件测试
  • ffmpeg(六):图片与视频互转命令
  • Python编程语言:2025年AI浪潮下的技术统治与学习红利
  • python的校园兼职系统
  • 分享两个可以一键生成sql server数据库 html格式巡检报告的脚本
  • 张之瞳全新单曲《6:30am》上线:以音乐定格青春遗憾中的诗意守望
  • Python 邻接表详细实现指南
  • 【软考高级系统架构论文】论面向服务架构设计及其应用
  • 【设计模式】6.原型模式
  • Git 使用手册:从入门到精通
  • 海光x86与Intel/AMD x86的差异解析:技术演进、架构博弈与未来之路
  • 通过 Lambda + API Gateway + 外部 API 实现。
  • 国产通用智能语音芯片品牌有哪些?
  • 树莓派无源蜂鸣器播放两首音乐实验指导书
  • python模块常用语法sys、traceback、QApplication
  • (LeetCode 面试经典 150 题) 169. 多数元素(哈希表 || 二分查找)
  • Java集合框架初识
  • 一,python语法教程.内置API
  • 【设计模式】3.装饰模式
  • 跳跳杆Pogo Stick
  • Swift 解锁数组可修改场景:LeetCode 307 高效解法全解析
  • (LeetCode 每日一题) 3085. 成为 K 特殊字符串需要删除的最少字符数 (贪心、哈希表)
  • 从0开始学习计算机视觉--Day02--数据驱动
  • MySQL之InnoDB存储引擎深度解析