给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
例：
图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> list = new ArrayList<>();
boolean flag = true; // 使用全局变量来标识是否符合有序
public boolean isValidBST (TreeNode root) {
// write code here
if (root == null ) {
return true;
}
if (root.left == null && root.right == null) {
return true;
}
// 二叉搜索树的先序遍历是有序的
func(root);
if (flag) {
return true;
}
return false;
}
public void func(TreeNode root) {
if (root == null) {
return;
}
func(root.left);
list.add(root.val);
// 在递归的时候就判断
if (list.size() > 1) {
int n1 = list.get(list.size() - 1);
int n2 = list.get(list.size() - 2);
if (n1 <= n2) {
flag = false;
return;
}
}
func(root.right);
return;
}
}
发表于 2025-04-21 19:31:43
回复(0)
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
/**
* NC184 判断是不是二叉搜索树
* @author d3y1
*/
public class Solution {
private boolean isBST = true;
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
// return solution1(root);
return solution2(root);
}
private TreeNode preNode;
/**
* 递归
* @param root
* @return
*/
private boolean solution1(TreeNode root){
inOrder(root);
return isBST;
}
/**
* 中序遍历
* @param root
*/
private void inOrder(TreeNode root){
if(!isBST){
return;
}
if(root == null){
return;
}
inOrder(root.left);
if(preNode == null){
preNode = root;
}else{
if(preNode.val >= root.val){
isBST = false;
return;
}else{
preNode = root;
}
}
inOrder(root.right);
}
////////////////////////////////////////////////////////////////////////////////////////
private Integer preVal = null;
/**
* 递归
* @param root
* @return
*/
private boolean solution2(TreeNode root){
inorder(root);
return isBST;
}
/**
* 中序遍历
* @param root
*/
private void inorder(TreeNode root){
if(!isBST){
return;
}
if(root == null){
return;
}
inorder(root.left);
if(preVal == null){
preVal = root.val;
}else{
if(preVal >= root.val){
isBST = false;
return;
}else{
preVal = root.val;
}
}
inorder(root.right);
}
}
发表于 2025-01-14 12:41:55
回复(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) {
if(root == null){
return true;
}
List<Integer> list = new ArrayList<>();
preOrder(list,root);
for(int i=1;i<list.size();i++){
if(list.get(i) < list.get(i-1)){
return false;
}
}
return true;
}
private void preOrder(List<Integer> list, TreeNode node) {
if (node != null) {
if (node.left != null) {
preOrder(list, node.left);
}
list.add(node.val);
if (node.right != null) {
preOrder(list, node.right);
}
}
}
} 思路2：递归判断每个节点是否符合二叉搜索树的性质 public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
if (root == null) {
return true;
}
preOrder(root);
preOrder2(root);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode p = stack.pop();
// 判断该节点是否合法
if(p.right != null){
if(min.get(p.right) < p.val){
return false;
}
stack.push(p.right);
}
if(p.left != null){
if(max.get(p.left) > p.val){
return false;
}
stack.push(p.left);
}
}
return true;
}
HashMap<TreeNode, Integer> max = new HashMap<>();
HashMap<TreeNode, Integer> min = new HashMap<>();
private int preOrder( TreeNode node) {
int val = node.val;
if (node.left != null) {
val = Math.max(preOrder(node.left), val);
}
if (node.right != null) {
val = Math.max(preOrder(node.right), val);
}
max.put(node, val);
return val;
}
// 返回node树中最大值
private int preOrder2( TreeNode node) {
int val = node.val;
if (node.left != null) {
val = Math.min(preOrder2(node.left), val);
}
if (node.right != null) {
val = Math.min(preOrder2(node.right), val);
}
min.put(node, val);
return val;
}
}
发表于 2024-09-18 21:19:14
回复(0)
public class Solution {
public boolean isValidBST (TreeNode root) {
return isValid(root);
}
TreeNode pre;
private boolean isValid(TreeNode root) {
if (root == null) {
return true;
}
boolean left = isValid(root.left);
if (pre != null && pre.val > root.val) {
return false;
}
pre = root;
boolean right = isValid(root.right);
return left && right;
}
}
发表于 2024-09-08 18:45:43
回复(0)
// 使用中序遍历，就相当于一维数组，即前面一位小于当前位
TreeNode pre = new TreeNode(Integer.MIN_VALUE);
public boolean isValidBST (TreeNode root) {
if(root == null) return true;
if(!isValidBST(root.left)) return false;
if(pre.val < root.val){
pre = root;
}else{
return false;
}
if(!isValidBST(root.right)) return false;
return true;
}
发表于 2024-08-27 15:36:53
回复(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 {
// 封装要获得的信息
public class Info {
public int max;
public int min;
public boolean isBST;
public Info() {
this.max = Integer.MAX_VALUE;
this.min = Integer.MIN_VALUE;
this.isBST = true;
}
public Info(int max, int min, boolean isBST) {
this.max = max;
this.min = min;
this.isBST = isBST;
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
public boolean isValidBST (TreeNode root) {
// write code here
// 1.我要干什么：
// 我要确定以root为根结点的子树是否是二叉搜索树
// 2.我需要什么信息：
// 获知【左子树】的【最大节点值】以及【是否二叉搜索树】
// 获知【右子树】的【最小节点值】以及【是否二叉搜索树】
// 综上所述，我需要左右子树的【最大和最小节点值】与【是否二叉搜索树】
// 3.我如何利用两个子树的信息加工出来我的信息：
// 若两棵子树均是二叉搜索树，且右 > root > 左，则true
return process(root).isBST;
}
public Info process (TreeNode root) {
// 递归出口
if (root == null) {
return new Info();
}
Info leftInfo = process(root.left);
Info rightInfo = process(root.right);
// 计算左右子树的真实最大值和最小值（如果为空，则置为root的值）
int trueLeftMax = leftInfo.max != Integer.MAX_VALUE ? leftInfo.max : root.val;
int trueLeftMin = leftInfo.min != Integer.MIN_VALUE ? leftInfo.min : root.val;
int trueRightMax = rightInfo.max != Integer.MAX_VALUE ? rightInfo.max : root.val;
int trueRightMin = rightInfo.min != Integer.MIN_VALUE ? rightInfo.min : root.val;
// 计算本子树的最大值和最小值
int myMax = Math.max(root.val, Math.max(trueLeftMax, trueRightMax));
int myMin = Math.min(root.val, Math.min(trueLeftMin, trueRightMin));
if (leftInfo.isBST == false || rightInfo.isBST == false) {
// 两棵子树只要有一个不是二叉搜索树，直接false
return new Info(myMax, myMin, false);
}
// 两棵子树都是二叉搜索树
// 注意！这里的等号是为了让子节点为null时（即左右最大或最小结点的值与本结点值相同）通过判断
if (trueLeftMax <= root.val && root.val <= trueRightMin) {
// 且满足右min > root > 左max，则true
return new Info(myMax, myMin, true);
}
return new Info(myMax, myMin, false);
}
}
发表于 2024-08-01 00:22:45
回复(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) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//左右节点高度
int lHeight = 1;
int rHeight = 1;
//如果右节点不为null,则队列下一个元素的左右子节点需高度减一
int count = 0;
boolean flag = true;
while (!queue.isEmpty()) {
TreeNode e = queue.poll();
count++;
if (e.left != null) {
lHeight++;
queue.add(e.left);
flag = toBST(root, e.left, lHeight, 0, 0, 0);
if (flag == false) {
return false;
}
}
if (e.right != null) {
rHeight++;
queue.add(e.right);
flag = toBST(root, e.right, rHeight, 0, 1, 1);
if (flag == false) {
return false;
}
if (count % 2 == 0) {
lHeight--;
rHeight--;
}
}
}
return true;
}
//通过高度对比和子节点左右位置对比确定是否与平衡二叉树一致
public boolean toBST(TreeNode root, TreeNode node, int height,
int currentHeight,
int position, int currentposition) {
currentHeight++;
if (currentHeight > height) {
return false;
}
if (node.val == root.val) {
//compare vertical height
if (currentHeight != height) {
return false;
}
//判断左右
if (position == currentposition) {
return true;
}
}
if (node.val < root.val) {
if (root.left == null) {
return false;
}
return toBST(root.left, node, height, currentHeight, position, 0);
}
if (node.val > root.val) {
if (root.right == null) {
return false;
}
return toBST(root.right, node, height, currentHeight, position, 1);
}
return true;
}
} 我的思路是根据从根节点遍历元素 来 构造二叉搜索树，根据节点高度和左右子节点位置是否一致来判断 1. 遍历元素且记录该元素高度和左右位置
2. 对比二叉平衡树看当前元素的高度和位置是否与二叉平衡树一致。不一致则返回false
发表于 2024-06-14 14:55:30
回复(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布尔型
*/
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)
问题信息
难度：
52条回答
815收藏
3828浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
