检查是否为BST

2023-05-16

题目描述

请实现一个函数,检查一棵二叉树是否为二叉查找树。

给定树的根结点指针TreeNode* root,请返回一个bool,代表该树是否为二叉查找树


代码如下:

package com.mianshi;

import java.util.Stack;

public class jingdian_21 {

	static class TreeNode {
	    int val = 0;
	    TreeNode left = null;
	    TreeNode right = null;
	    public TreeNode(int val) {
	        this.val = val;
	    }
	}
	    
	public static void main(String[] args) {
		TreeNode l1=new TreeNode(4);
		TreeNode l2=new TreeNode(2);
		TreeNode l3=new TreeNode(6);
		TreeNode l4=new TreeNode(1);
		TreeNode l5=new TreeNode(3);
		TreeNode l6=new TreeNode(5);
		TreeNode l7=new TreeNode(7);
		l1.left=l2;
		l1.right=l3;
		l2.left=l4;
		l2.right=l5;
		l3.left=l6;
	  	l3.right=l7;
        System.out.print(jingdian_21.isValidBST(l1));
	}
	public static boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        Stack<TreeNode> stack =new Stack<TreeNode>();
        int pre=0;
        TreeNode p=root;
        boolean isFirst=true;
        while(p!=null || !stack.isEmpty()){
        	  while(p!=null){
        		  stack.push(p);
        		  p=p.left;
        	  }
        	  p=stack.pop();
        	  if(isFirst){
        		  pre=p.val;
        		  isFirst=false;
        	  }else if(pre>p.val){
        		  return false;
        	  }else{
        		  pre=p.val;
        	  }
        	  p=p.right;
        }
        return true;
	}
}


本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

检查是否为BST 的相关文章

  • JAVA语言之基数排序

    基数排序简而言之可以创建0 9余数共十个桶 代码如下 xff1a public class jishu 1 public static void main String args int A 61 new int 54 35 48 36 2
  • 链式A+B之程序员面试经典

    有两个用链表表示的整数 xff0c 每个结点包含一个数位 这些数位是反向存放的 xff0c 也就是个位排在链表的首部 编写函数对这两个整数求和 xff0c 并用链表形式返回结果 给定两个链表ListNode A xff0c ListNode
  • Android逆向【4】:暴力破解APK签名校验,愉快的重新打包微信支付宝APK

    回顾 Android逆向小技巧 xff1a 批量注入日志 xff0c 打印目标程序执行流程 在上一篇2019年的文章中 xff0c 我们使用python写了一个简单的文本处理工具 xff1a https github com encoder
  • Anaconda相关shell命令相关知识点

    文章目录 前言一 Anaconda或Miniconda镜像下载二 配置Anaconda源1 查看安装过的镜像1 显示镜像源 xff0c 如果是新安装Anaconda则默认使用国外镜像源 xff0c 它会显示2 若有新的镜像源 xff0c 它
  • 回文链表之程序员面试经典

    题目描述 请编写一个函数 xff0c 检查链表是否为回文 给定一个链表ListNode pHead xff0c 请返回一个bool xff0c 代表链表是否为回文 测试样例 xff1a 1 2 3 2 1 返回 xff1a true 1 2
  • 集合栈之程序员面试经典

    题目描述 请实现一种数据结构SetOfStacks xff0c 由多个栈组成 xff0c 其中每个栈的大小为size xff0c 当前一个栈填满时 xff0c 新建一个栈 该数据结构应支持与普通栈相同的push和pop操作 给定一个操作序列
  • JAVA语言之全排列的递归实现

    问题 xff1a 假如有一个数组的值为1 2 2 3 4 5一共六个值 xff0c 进行全排列 xff0c 但要求是3和5不能在一起 xff0c 并且4不能在第三个位置 代码如下 public class testtest public s
  • 猫狗收容所之程序员面试经典

    题目描述 有家动物收容所只收留猫和狗 xff0c 但有特殊的收养规则 xff0c 收养人有两种收养方式 xff0c 第一种为直接收养所有动物中最早进入收容所的 xff0c 第二种为选择收养的动物类型 xff08 猫或狗 xff09 xff0
  • 双栈排序之程序员面试经典

    题目描述 请编写一个程序 xff0c 按升序对栈进行排序 xff08 即最大元素位于栈顶 xff09 xff0c 要求最多只能使用一个额外的栈存放临时数据 xff0c 但不得将元素复制到别的数据结构中 给定一个int numbers C 4
  • 用两个栈实现队列之程序员面试经典

    题目描述 用两个栈来实现一个队列 xff0c 完成队列的Push和Pop操作 队列中的元素为int类型 比如有栈A和栈B xff0c 在模拟队列的时候先将所有数据依次放入栈A中 xff0c 在要弹出的时候将A中的数据依次从上到下放进栈B x
  • 高度最小的BST之程序员面试经典

    题目描述 对于一个元素各不相同且按升序排列的有序序列 xff0c 请编写一个算法 xff0c 创建一棵高度最小的二叉查找树 给定一个有序序列int vals 请返回创建的二叉查找树的高度 二叉排序树 xff08 Binary Sort Tr
  • 二叉树平衡检查之程序员面试经典

    题目描述 实现一个函数 xff0c 检查二叉树是否平衡 xff0c 平衡的定义如下 xff0c 对于树中的任意一个结点 xff0c 其两颗子树的高度差不超过1 给定指向树根结点的指针TreeNode root xff0c 请返回一个bool
  • JAVA语言之三色排序

    有一个只由0 xff0c 1 xff0c 2三种元素构成的整数数组 xff0c 请使用交换 原地排序而不是使用计数进行排序 给定一个只含0 xff0c 1 xff0c 2的整数数组A 及它的大小 xff0c 请返回排序后的数组 保证数组大小

随机推荐

  • Linux 服务器下载并安装jdk8 学习教程

    获得一台linux服务器 要在linux下安装jdk xff0c 首先你得先有一台linux服务器 xff0c 虚拟机或者租一台都可以 yum安装jdk xff08 力荐 xff09 在linux上使用yum安装是非常粗暴无脑的 xff0c
  • JAVA语言之有序矩阵查找

    现在有一个行和列都排好序的矩阵 xff0c 请设计一个高效算法 xff0c 快速查找矩阵中是否含有值x 给定一个int矩阵mat xff0c 同时给定矩阵大小n xm 及待查找的数x xff0c 请返回一个bool值 xff0c 代表矩阵中
  • JAVA语言之最短子数组长度

    对于一个数组 xff0c 请设计一个高效算法计算需要排序的最短子数组的长度 给定一个int数组A 和数组的大小n xff0c 请返回一个二元组 xff0c 代表所求序列的长度 原序列位置从0开始标号 若原序列有序 xff0c 返回0 保证A
  • JAVA语言之相邻两数最大差值

    有一个整形数组A xff0c 请设计一个复杂度为O n 的算法 xff0c 算出排序后相邻两数的最大差值 给定一个int数组A 和A 的大小n xff0c 请返回最大的差值 保证数组元素多于1个 测试样例 xff1a 1 2 5 4 6 5
  • Spring MVC 流程图

    Spring MVC工作流程图 图一 图二 Spring工作流程描述 1 用户向服务器发送请求 xff0c 请求被Spring 前端控制Servelt DispatcherServlet捕获 xff1b 2 DispatcherServle
  • 输出单层结点之程序员面试经典

    题目描述 对于一棵二叉树 xff0c 请设计一个算法 xff0c 创建含有某一深度上所有结点的链表 给定二叉树的根结点指针TreeNode root xff0c 以及链表上结点的深度 xff0c 请返回一个链表ListNode xff0c
  • java中没有2进制的数据类型,对二进制的操作,需要使用共三种操作符

    lt lt 左移位操作符 gt gt 右移位操作符 gt gt gt 无符号右移操作符 使用左移时 xff0c 数会变大 xff0c 很多时间 xff0c 用来代替 乘方 的操作 比如 2的平方 61 2 2 61 4 61 2 lt lt
  • 面向对象的特征有哪些方面

    需要学习资料的 43 微信公众号 学习资源后台找我 本人比较忙 我看到了会在后台帮你 xff0c 谢谢关注啦 抽象 xff1a 抽象是将一类对象的共同特征总结出来构造类的过程 xff0c 包括数据抽象和行为抽象两方面 抽象只关注对象有哪些属
  • 句子的逆序

    对于一个字符串 xff0c 请设计一个算法 xff0c 只在字符串的单词间做逆序调整 xff0c 也就是说 xff0c 字符串由一些由空格分隔的部分组成 xff0c 你需要将这些部分逆序 给定一个原字符串A 和他的长度 xff0c 请返回逆
  • 字符串移位

    对于一个字符串 xff0c 请设计一个算法 xff0c 将字符串的长度为len的前缀平移到字符串的最后 给定一个字符串A 和它的长度 xff0c 同时给定len xff0c 请返回平移后的字符串 测试样例 xff1a 34 ABCDE 34
  • 拼接最小字典序

    对于一个给定的字符串数组 xff0c 请找到一种拼接顺序 xff0c 使所有小字符串拼接成的大字符串是所有可能的拼接中字典序最小的 给定一个字符串数组strs xff0c 同时给定它的大小 xff0c 请返回拼接成的串 测试样例 xff1a
  • go语言时间类型和时间戳

    时间类型 获取当地时间 fmt span class token punctuation span span class token function Println span span class token punctuation sp
  • 是否可以从一个静态(static)方法内部发出对非静态(non-static)方法的调用?

    不可以 xff0c 静态方法只能访问静态成员 xff0c 因为非静态方法的调用要先创建对象 xff0c 在调用静态方法时可能对象并没有被初始化
  • GC是什么?为什么要有GC?

    GC 是垃圾收集的意思 xff0c 内存处理是编程人员容易出现问题的地方 xff0c 忘记或者错误的内存回收会导致程序或系统的不稳定甚至崩溃 xff0c Java 提供的GC功能可以自动监测对象是否超过作用域从而达到自动回收内存的目的 xf
  • 空格替换

    请编写一个方法 xff0c 将字符串中的空格全部替换为 20 假定该字符串有足够的空间存放新增的字符 xff0c 并且知道字符串的真实长度 小于等于1000 xff0c 同时保证字符串由大小写的英文字母组成 给定一个string iniSt
  • 合法括号序列判断

    对于一个字符串 xff0c 请设计一个算法 xff0c 判断其是否为一个合法的括号串 给定一个字符串A 和它的长度n xff0c 请返回一个bool值代表它是否为一个合法的括号串 测试样例 xff1a 34 34 6 返回 xff1a tr
  • 最长无重复字符子串

    对于一个字符串 请设计一个高效算法 xff0c 找到字符串的最长无重复字符的子串长度 给定一个字符串A 及它的长度n xff0c 请返回它的最长无重复字符子串长度 保证A中字符全部为小写英文字符 xff0c 且长度小于等于500 测试样例
  • 列出一些你常见的运行时异常(非检查异常)?

    ArithmeticException xff08 算术异常 xff09 ClassCastException xff08 类转换异常 xff09 IllegalArgumentException xff08 非法参数异常 xff09 In
  • 阐述final、finally、finalize的区别

    final xff1a 修饰符 xff08 关键字 xff09 有三种用法 xff1a 如果一个类被声明为final xff0c 意味着它不能再派生出新的子类 xff0c 即不能被继承 xff0c 因此它和abstract是反义词 将变量声
  • 检查是否为BST

    题目描述 请实现一个函数 xff0c 检查一棵二叉树是否为二叉查找树 给定树的根结点指针TreeNode root xff0c 请返回一个bool xff0c 代表该树是否为二叉查找树 代码如下 xff1a package com mian