给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
例：
图1
图2
数据范围：节点数量满足 
，节点上的值满足 
[编程题]判断是不是二叉搜索树
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
List<Integer> res = new ArrayList<>();
boolean flag = true;
public boolean isValidBST (TreeNode root) {
// write code here
if ( root == null ) return true;
midBST( root );
return flag;
}
private void midBST(TreeNode root) {
if (root.left != null) midBST( root.left );
if ( res.size() > 0 && res.get(res.size() - 1) > root.val ) flag = false;
res.add( root.val );
if (root.right != null) midBST( root.right );
}
} 直接检查中序遍历的结果是否有序
发表于 2024-04-25 21:37:06
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
returnType res = judge(root);
return res.isBST;
}
public returnType judge(TreeNode root) {
// 递归：向左右子树索要信息：是否是BST；左子树最大值；右子树最小值
returnType res = new returnType();
if (root == null){
res.isBST = true;
return res;
}
returnType resLeft = judge(root.left);
// 由于递归获取左树最大，右树最小，所以左右都要同时统计最大最小（左树也有右子树，右树也有左子树）：取信息并集
res.max = Math.max(root.val, resLeft.max); // 左树最大最小值
res.min = Math.min(root.val, resLeft.min);
if(!resLeft.isBST || root.val < resLeft.max){ // 左树假或者根小于左，返回假
return res; // returnType 默认 false
}
returnType resRight = judge(root.right);
res.max = Math.max(root.val, resRight.max); // 右树最大最小值
res.min = Math.min(root.val, resRight.min);
if(!resRight.isBST || root.val > resRight.min){ // 右树假或者根大于右边，返回假
return res; // returnType 默认 false
}
res.isBST = true;
return res;
}
public class returnType {
int max = Integer.MIN_VALUE; // 坑：最大要设为最小，最小要设为最大
int min = Integer.MAX_VALUE;
boolean isBST = false;
}
}
编辑于 2024-04-11 18:06:03
回复(0)
public class Solution {
private TreeNode pre = null;
/**
* 给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
if (null == root) {
return false;
}
return inorder(root);
}
public boolean inorder(TreeNode curr) {
if (null == curr) {
return true;
}
boolean isLeftOK = inorder(curr.left);
if (pre != null && pre.val >= curr.val) {
return false;
}
pre = curr;
boolean isRightOK = inorder(curr.right);
return isLeftOK && isRightOK;
}
}
发表于 2023-10-18 17:29:39
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
boolean b = true;
TreeNode t;
public boolean isValidBST (TreeNode root) {
// write code here
//或者采用中序遍历搜索树一定有序来判断
t = root;
a(root);
return b;
}
public void a(TreeNode root) {
if (root == null||b==false)
return;
if (root.left != null) {
if (root.left.val > root.val) {
b = false;
return;
}
if (t.val < root.val) {
if (root.left.val < t.val) {
b = false;
return;
}
}
}
if (root.right != null) {
if (root.right.val < root.val) {
b = false;
return;
}
if (t.val > root.val) {
if (root.right.val > t.val) {
b = false;
return;
}
}
}
t = root;
a(root.left);
a(root.right);
}
}
发表于 2023-10-12 15:00:43
回复(0)
public class Solution {
Integer prev = null;
boolean result = true;
public boolean isValidBST (TreeNode root) {
// 二叉搜索树的中序遍历就是升序的，如果不满足当前节点大于前一个，那么就不是二叉搜索树
iterate(root);
return result;
}
private void iterate(TreeNode root) {
if (root == null) {
return;
}
if (result) {
iterate(root.left);
if (prev != null && root.val <= prev) {
result = false;
}
prev = root.val;
iterate(root.right);
}
}
}
发表于 2023-09-20 21:40:36
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
TreeNode pre = null;
public boolean isValidBST (TreeNode root) {
// write code here
if(root==null)return true;
if(!isValidBST(root.left))return false;
if(pre!=null&&pre.val>root.val)return false;
pre=root;
if(!isValidBST(root.right))return false;
return true;
}
}
发表于 2023-07-29 21:07:35
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
int min =Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
//return InOrder(root);
return Dfs(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public boolean Dfs (TreeNode root, int min, int max) {
if (root == null) return true;
if (root.val < min || root.val > max) return false;
return Dfs(root.left, min, root.val) && Dfs(root.right, root.val, max);
}
public boolean InOrder (TreeNode root) {
if (root == null) return true;
if (!InOrder(root.left)) {
return false;
}
if (root.val < min) {
return false;
} else {
min=root.val;
}
if(!InOrder(root.right)) return false;
return true;
}
}
发表于 2023-07-27 13:00:49
回复(0)
public boolean isValidBST (TreeNode root) {
List<Integer> list=new ArrayList<>();
build(root,list);
for(int i=0;i<list.size()-1;i++){//list中的元素应该是递增的
if(list.get(i)>=list.get(i+1)){
return false;
}
}
return true;
}
public void build(TreeNode root,List<Integer> list){
if(root==null){
return;
}
//中序遍历 左 头 右
build(root.left,list);
list.add(root.val);
build(root.right,list);
}
发表于 2023-07-12 14:58:02
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
// write code here
if (root == null) return true;
int rootVal = root.val;
boolean res = true;
if (root.left != null) {
if (rootVal < root.left.val) return false;
}
if (root.right != null) {
if (rootVal > root.right.val) return false;
}
if (root.left != null) {
res = getValidBST(root.left, rootVal, true);
}
if (!res) return res;
if (root.right != null) {
res = getValidBST(root.right, rootVal, false);
}
return res;
}
private boolean getValidBST(TreeNode root, int rootVal, boolean flag) {
if (root == null) return true;
int val = root.val;
if (flag) {
if(val > rootVal) return false;
if (root.left != null) {
if (val < root.left.val) return false;
}
if (root.right != null) {
if (val > root.right.val ) return false;
}
} else {
if(val < rootVal) return false;
if (root.left != null) {
if (val < root.left.val ) return false;
}
if (root.right != null) {
if (val > root.right.val) return false;
}
}
boolean res1 = getValidBST(root.left, rootVal, flag);
boolean res2 = getValidBST(root.right, rootVal, flag);
return res1 && res2;
}
}
发表于 2023-03-22 23:39:18
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public static class Info {
public boolean isBST;// 是否是二叉搜索树
public int max;// 最大值
public int min;// 最小值
public Info(boolean isBST, int max, int min) {
this.isBST = isBST;
this.max = max;
this.min = min;
}
}
public static Info process(TreeNode x) {
// 节点为空,我们索性返回空
// 之后再进行判空
if(x == null) {
return null;
}
// 先获取到该节点信息
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
// 假设该节点是最大值,之后再更改
int max = x.val;
int min = x.val;
// 如果左树不为空,就代表左树有东西
if(leftInfo != null) {
max = Math.max(leftInfo.max, max);// 更换最大值:谁更大换谁
min = Math.min(leftInfo.min, min);// 更换最小值:谁更小换谁
}
// 如果右树不为空,就代表右树有东西
if(rightInfo != null) {
max = Math.max(rightInfo.max, max);// 更换最大值:谁更大换谁
min = Math.min(rightInfo.min, min);// 更换最小值:谁更小换谁
}
boolean isBST = true;// 先默认是二叉搜索树
// 把非二叉搜索树的情况列举出来,让 isBST=false
// 左树不为空&&左树不是二叉搜索树
if(leftInfo != null && !leftInfo.isBST) {
isBST = false;
}
// 右树不为空&&右树不是二叉搜索树
if(rightInfo != null && !rightInfo.isBST) {
isBST = false;
}
// 左树为空,返回true
// 左树不为空,比较左树最大值和节点值
// 左树最大值>节点值->返回 false
// 左树最大值<节点值->返回true
boolean leftMaxLessX = (leftInfo == null) ? true : (leftInfo.max < x.val);
// 右树为空,返回true
// 右树不为空,比较右树最小值和节点值
// 右树最小值>节点值->返回true
// 右树最小值<节点值->返回false
boolean rightMinMoreX = (rightInfo == null) ? true : (rightInfo.min > x.val);
if(!leftMaxLessX || !rightMinMoreX) {
isBST = false;
}
return new Info(isBST,max,min);
}
public static boolean isValidBST(TreeNode root) {
return process(root).isBST;
}
}
发表于 2023-01-11 16:39:47
回复(0)
鉴于牛客喜欢出 O(1) 空间的二叉树， 这里贴一个O(1)空间的答案。
import java.util.*;
public class Solution {
public boolean isValidBST (TreeNode head) {
if(head == null){
return true;
}
TreeNode cur = head, mostRight = null, prevNode = null;
while (cur != null){
mostRight = cur.left;
if(mostRight != null){
while (mostRight.right !=null && mostRight.right != cur){
mostRight = mostRight.right;
}
if(mostRight.right == null){
mostRight.right = cur;
cur = cur.left;
continue;
}else {
mostRight.right = null;
}
}
if (prevNode != null && prevNode.val >= cur.val) {
return false;
}
prevNode = cur;
cur = cur.right;
}
return true;
}
}
发表于 2022-12-20 04:54:09
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
// write code here
if(root==null || (root.left==null && root.right==null)){
return true;
}
//list用来接收中序遍历的结果
ArrayList<Integer> list=new ArrayList<>();
infixOrder(list,root);
//如果集合按照从小到大的顺序排列,则返回true
for(int i=1;i<list.size();i++){
if(list.get(i-1)>list.get(i)){
return false;
}
}
return true;
}
//中序遍历
public void infixOrder(ArrayList<Integer> list,TreeNode root){
if(root==null){
return;
}
infixOrder(list,root.left);
list.add(root.val);
infixOrder(list,root.right);
}
}
发表于 2022-11-11 14:08:49
回复(0)
递归实现。定义pre 保留上一个节点的值
// 辅助变量，pre指向前一个节点的值，初始值为Integer.MIN_VALUE，也就是说当第一次比较时 pre一定比 root.val小
Integer pre = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
// 等于空，则返回true
if(root == null) return true;
// 向左递归，如果返回false 就return false
if(!isValidBST (root.left)) return false;
// 当前一个值pre 大于 当前节点的值 就返回false
if(pre > root.val) return false;
// 否则将前一个值修改为当前节点的值，
pre = root.val;
// 最后开始向右递归，并返回结果即可
return isValidBST (root.right);
}
发表于 2022-11-06 10:51:29
回复(0)
搜索二叉树中序遍历为递增的，中序遍历后判断是否递增即可
public boolean isValidBST (TreeNode root) {
ArrayList<Integer>list = new ArrayList<>();
inorder(root,list);
for(int i = 0;i<list.size()-1;i++){
if(list.get(i)>list.get(i+1)){
return false;
}
}
return true;
}
public void inorder(TreeNode root,ArrayList<Integer>list){
if(root==null){
return;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
}
发表于 2022-10-21 11:03:58
回复(0)
//先递归先序遍历存入list,然后判断list是否有序就可以了
//我菜只能这么做了T_T
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public void mid(ArrayList<Integer> list,TreeNode root){
if(root == null){
return ;
}
mid(list,root.left);
list.add(root.val);
mid(list,root.right);
}
public boolean isValidBST (TreeNode root) {
// write code here
if(root == null){
return true;
}
ArrayList<Integer> list = new ArrayList<Integer>();
mid(list,root);
for(int i = 0;i < list.size()-1;i++){
if(list.get(i)>list.get(i+1)){
return false;
}
}
return true;
}
}
发表于 2022-09-17 11:59:18
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
int pre = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
if (root == null) return true;
boolean left = isValidBST(root.left);
if (left == false) {
return false;
}
if (root.val < pre) {
return false;
}
pre = root.val;
boolean right = isValidBST(root.right);
return right;
}
}
发表于 2022-09-12 14:58:31
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST(TreeNode root){
//利用二叉搜索树的中序遍历是非递减数列的特性解题
ArrayList<Integer> list=new ArrayList<>();
inorderfun(root,list);
if(root==null||(root.left==null&&root.right==null))return true;
for(int i=1;i<list.size();i++){
if(list.get(i)<list.get(i-1))
return false;
}
return true;
}
public void inorderfun(TreeNode node,ArrayList<Integer> list){
if(node==null)return;
inorderfun(node.left,list);
list.add(node.val);
inorderfun(node.right,list);
}
}
发表于 2022-08-30 22:35:04
回复(0)
判断是否是二叉搜索树
中序遍历，先一直走left，把pre初始化（int pre = Integer.MIN_VALUE）
pre表示中序遍历序列中前一个数，root.val表示当前数。
pre>root.val和isValidBST(root.left)都返回false。
其实就是中序遍历，维护中序遍历序列中前一个数pre。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
//pre为中序遍历中前一个的值
int pre = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
//中序遍历，如果后面的数小于前面的数，则返回false
//遍历到头，成功
if(root == null) return true;
//先遍历左边
if(!isValidBST(root.left)) return false;
if(pre > root.val) return false;
//更新中序遍历中root的前一个值pre
pre = root.val;
//再进行右子树的遍历
return isValidBST(root.right);
}
}
发表于 2022-07-24 21:04:34
回复(0)
问题信息
难度：
45条回答
631收藏
1970浏览
通过挑战的用户
查看代码-
2023-02-21 18:08:14 -
2022-09-17 17:11:45
-
2022-09-16 17:18:31
-
2022-09-16 16:38:59
-
2022-09-16 16:24:46
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
