25_验证二叉搜索树

简介: 25_验证二叉搜索树

98.验证二叉搜索树

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

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

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

示例 1:

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

示例 2:

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

思路

要知道要知道中序遍历下,输出的二叉搜索树节点的数值是有序序列。

有了这个特性,验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。

递归法

class Solution {
  //递归
  TreeNode max;
  public boolean isValidBST(TreeNode root) {
    if (root == null) {
      return true;
    }
    // 左
    boolean left = isValidBST(root.left);
    if (!left) {
      return false;
    }
    // 中
    if (max != null && root.val <= max.val) {
      return false;
    }
    max = root;
    // 右
    boolean right = isValidBST(root.right);
    return 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;
  }
}
相关文章
|
存储 固态存储 数据安全/隐私保护
自己动手 DIY 一个读写200MB/s 的高速 U 盘
自己动手 DIY 一个读写200MB/s 的高速 U 盘
2829 0
自己动手 DIY 一个读写200MB/s 的高速 U 盘
|
云安全 安全 API
阿里云——OpenAPI使用——短信服务
阿里云——OpenAPI使用——短信服务
836 0
|
JavaScript 前端开发 Java
前端框架选择之争:jQuery与Vue在现代Web开发中的真实地位-优雅草卓伊凡
前端框架选择之争:jQuery与Vue在现代Web开发中的真实地位-优雅草卓伊凡
1001 72
前端框架选择之争:jQuery与Vue在现代Web开发中的真实地位-优雅草卓伊凡
|
10月前
|
SQL 存储 缓存
PL/pgSQL 入门教程(六):从避坑到吃透,聊聊事务、错误处理和底层那些事儿
本文深度解析PL/pgSQL开发避坑指南:详解RAISE多级错误处理与USING增强提示、EXCEPTION事务恢复机制、变量替换限制与计划缓存陷阱,并分享美元符引号、CREATE OR REPLACE调试、extra_warnings预警等实战技巧,助你写出健壮高效存储过程。
|
人工智能 IDE 程序员
Qoder 负责人揭秘:Qoder 产品背后的思考与未来发展
AI Coding 已经成为软件研发的必选项。根据行业的调研,目前全球超过 62% 的开发者正在使用 AI Coding 产品,开发者研发效率提升 30% 以上。当然,有很多开发者用得比较深入,提效超过 50%。
1990 22
|
自然语言处理 语音技术 开发工具
IndexTTS2.0_ 情感表达与时长可控的自回归零样本语音合成突破
IndexTTS2 是首个实现自回归模型下**时长可控**、**情感与音色解耦**的零样本语音合成系统。支持语音克隆、情感迁移与文本驱动情绪控制,适用于影视配音、虚拟主播等场景。开源代码与模型已发布,提供完整本地部署方案,大幅提升语音合成的实用性与表现力。
3388 5
|
编解码 人工智能 监控
VISION XL:支持四倍超分辨率的 AI 视频修复处理工具,提供去除模糊、修复缺失等功能
VISION XL是一款基于潜在扩散模型的高效视频修复和超分辨率工具,能够修复视频缺失部分、去除模糊,并支持四倍超分辨率。该工具优化了处理效率,适合快速处理视频的应用场景。
3351 6
VISION XL:支持四倍超分辨率的 AI 视频修复处理工具,提供去除模糊、修复缺失等功能
|
机器学习/深度学习 人工智能 自然语言处理
AI训练师入行指南(三):机器学习算法和模型架构选择
从淘金到雕琢,将原始数据炼成智能珠宝!本文带您走进数字珠宝工坊,用算法工具打磨数据金砂。从基础的经典算法到精密的深度学习模型,结合电商、医疗、金融等场景实战,手把手教您选择合适工具,打造价值连城的智能应用。掌握AutoML改装套件与模型蒸馏术,让复杂问题迎刃而解。握紧算法刻刀,为数字世界雕刻文明!
669 6
|
算法 计算机视觉
YOLOv3 的非极大值抑制(NMS)算法是如何工作的,它对最终检测结果有何影响?
YOLOv3 的非极大值抑制(NMS)算法是如何工作的,它对最终检测结果有何影响?
|
传感器 人工智能 边缘计算
AI赋能油田巡检——无人机视频监控系统的技术解析
无人机油田巡检系统融合无人机硬件与AI视频监控技术,实现全域覆盖、智能分析和高效管理。通过多旋翼/固定翼无人机搭载高分辨率摄像头及传感器,采集多维数据;结合YOLOv9等算法进行异常检测,准确率高达98%。系统支持5G实时传输、边缘计算及集中化管理平台,提供可视化监控与预测性维护。基于开源框架设计,灵活扩展且成本低,大幅提升油田巡检效率与安全性。
1524 0