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;
  }
}
相关文章
|
存储 安全 Shell
深入浅出操作系统:从原理到实践
【9月更文挑战第21天】在数字时代的浪潮中,操作系统扮演着至关重要的角色。本文将深入探究操作系统的奥秘,从其基本概念和核心原理出发,逐步引导读者理解操作系统的工作机制。我们将通过生动的例子和实用的代码片段,揭示操作系统如何管理计算机硬件资源、提供用户接口以及确保系统安全与性能优化。无论你是初学者还是有一定基础的开发者,这篇文章都将为你打开一扇通往操作系统深层世界的大门。准备好跟随我们的脚步,一起探索这个让计算机变得生动起来的神奇软件吧!
345 8
|
2月前
|
API 定位技术 调度
实现精准定位的—坐标系经纬度转换API技术说明和行业应用
在地图服务、物流调度等应用中,多源地理位置数据因采用不同坐标系(如WGS84、GCJ02、BD09)需统一转换,以避免位置偏移影响路径规划与分析精度。本文介绍坐标转换背景、技术方案及Python调用示例,强调其在智慧交通与物流系统中的重要性。
323 0
|
jenkins Java Shell
使用 Docker 安装 Jenkins 并实现项目自动化部署
Jenkins 是一款开源的持续集成(DI)工具,广泛用于项目开发,能提供自动构建,测试,部署等功能。作为领先的开源自动化服务器,Jenkins 提供了数百个插件来支持构建、部署和自动化任何项目。
35289 3
使用 Docker 安装 Jenkins 并实现项目自动化部署
|
自动驾驶 5G
5G技术中的时分双工(TDD)与频分双工(FDD)的应用区别
5G技术中的时分双工(TDD)与频分双工(FDD)的应用区别
1971 63
|
8月前
|
机器学习/深度学习 数据采集 运维
机器学习在网络流量预测中的应用:运维人员的智慧水晶球?
机器学习在网络流量预测中的应用:运维人员的智慧水晶球?
328 19
|
12月前
|
移动开发 小程序 测试技术
自定义多级联动选择器指南(uni-app)
在本文中,探讨了如何在uni-app中创建自定义多级联动选择器组件。这个组件具有强大的多端支持,可适用于H5、APP、微信小程序、支付宝小程序等多种平台。
908 1
自定义多级联动选择器指南(uni-app)
|
设计模式 测试技术 开发者
探索Python中的装饰器:从基础到高级应用
本文旨在深入探讨Python中一个强大而灵活的特性——装饰器(Decorators)。通过逐步解析其工作原理、常见用法以及如何自定义装饰器,我们希望帮助读者不仅能够理解装饰器的基本概念,还能掌握如何在实际编程中高效利用这一工具来优化代码结构、增强程序的可读性和可维护性。无论是Python初学者还是经验丰富的开发者,都能在本文中找到有价值的信息和启示。
|
存储 数据挖掘 数据处理
【Python DataFrame 专栏】优化 DataFrame 性能:提升数据处理效率的秘诀
【5月更文挑战第19天】优化 Python DataFrame 性能的关键点包括:选择合适的数据类型以节省内存,避免重复计算,利用向量化操作,考虑使用 `iterrows` 或 `itertuples` 迭代,优化索引以及借助 `Cython` 或 `Numba` 加速代码执行。通过这些策略,能提升数据处理效率,应对大规模数据挑战。
518 2
【Python DataFrame 专栏】优化 DataFrame 性能:提升数据处理效率的秘诀
|
Java Linux
linux 对子用户配置java 环境变量
linux 对子用户配置java 环境变量
157 3
|
人工智能 数据安全/隐私保护
你试过一秒钟出现在世界各地的感觉吗?
【8月更文挑战第13天】你试过一秒钟出现在世界各地的感觉吗?