给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
例：
图1
图2
数据范围：节点数量满足 
，节点上的值满足 
[编程题]判断是不是二叉搜索树
static List<Integer> list=new ArrayList<>();
public boolean isValidBST (TreeNode root) {
InOrder(root);
for(int i=0;i<list.size()-1;i++){
if(list.get(i)>list.get(i+1))return false;
}
return true;
}
void InOrder(TreeNode root){
if(root!=null){
InOrder(root.left);
list.add(root.val);
InOrder(root.right);
}
}
发表于 2022-06-02 18:57:34
回复(0)
public class Solution {
/**
* 中序遍历，pre为前置的节点，如果存在 pre.val>cur.val 则返回false
*
* @param root TreeNode类
* @return bool布尔型
*/
TreeNode pre = null;
boolean result = true;
public boolean isValidBST(TreeNode root) {
inOrder(root);
return result;
}
public void inOrder(TreeNode root) {
if (root == null)
return;
inOrder(root.left);
if (pre == null) {
pre = root;
return;
}
if (pre.val > root.val) {
result = false;
return;
}
pre = root;
inOrder(root.right);
}
}
发表于 2022-02-22 14:09:23
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
vector<int>tmp;
void dfs(TreeNode*root)
{
if(!root)return ;
dfs(root->left);
tmp.push_back(root->val);
dfs(root->right);
}
bool isValidBST(TreeNode* root) {
// write code here
dfs(root);
for(int i=1;i<tmp.size();i++)
{
if(tmp[i]<tmp[i-1])return false;
}
return true;
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
vector<int>tmp;
void dfs(TreeNode*root)
{
if(!root)return ;
dfs(root->left);
tmp.push_back(root->val);
dfs(root->right);
}
bool isValidBST(TreeNode* root) {
// write code here
dfs(root);
for(int i=1;i<tmp.size();i++)
{
if(tmp[i]<tmp[i-1])return false;
}
return true;
}
};
发表于 2021-12-21 07:45:10
回复(0)
检查中序遍历是否满足单调递增的性质就可以了，用一个prev变量记录前一个节点的值，便于在中序遍历的过程中就能判断出来，时间复杂度和空间复杂度都是O(n)。
迭代版中序遍历
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
Stack<TreeNode> stack = new Stack<>();
int prev = Integer.MIN_VALUE;
while(!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
root = stack.pop();
if(root.val <= prev) {
return false; // 破坏了BST中序遍历的单调递增性质，直接返回false
}
prev = root.val;
root = root.right;
}
}
return true; // 没有发现单调性被破坏，是BST
}
} Morris遍历版中序遍历
Morris遍历利用叶子节点的空闲指针，可以把迭代版和递归版的中序遍历的空间复杂度O(n)优化至O(1)，时间复杂度仍然为O(n)。
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
int prev = Integer.MIN_VALUE;
TreeNode cur = root;
TreeNode mostRight = null;
while(cur != null){
mostRight = cur.left;
if(mostRight != null){
// 到左子树的最右节点
while(mostRight.right != null && mostRight.right != cur) {
mostRight = mostRight.right;
}
if(mostRight.right == null){
// 第一次到左子树的最右节点，需要将其右孩子的指向指向cur
mostRight.right = cur;
cur = cur.left;
continue;
}else{
if(cur.val <= prev) {
return false;
}
prev = cur.val;
// 第二次到这要恢复右孩子的指针
mostRight.right = null;
}
}else{
// 只会到一次的节点，直接判断
if(cur.val <= prev){
return false;
}
prev = cur.val;
}
// 没有左子树节点直接右移
cur = cur.right;
}
return true;
}
}
编辑于 2021-12-11 10:00:22
回复(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布尔型
*/
static int min = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
if(root == null){
return true;
}
if( !(isValidBST(root.left)) ){
return false;
}
if(root.val <= min){
return false;
}else{
min = root.val;
}
if( !(isValidBST(root.right)) ){
return false;
}
return true;
}
}
上述是递归的实现
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布尔型
*/
static int min = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
if(root == null){
return true;
}
// Stack<TreeNode> stack = new Stack<TreeNode>();
// while(! stack.isEmpty() || root!=null){
// //入栈向左一直走
// if(root != null){
// stack.push(root);
// root = root.left;
// }else{
// //访问右子树
// root = stack.pop();
// if(root.val <= min){
// return false;
// }else{
// min = root.val;
// root = root.right;
// }
// }
// }
if( !(isValidBST(root.left)) ){
return false;
}
if(root.val <= min){
return false;
}else{
min = root.val;
}
if( !(isValidBST(root.right)) ){
return false;
}
return true;
}
}
发表于 2021-11-19 00:18:45
回复(0)
前序遍历验证每个节点是否符合该二叉搜索树的约束【min < root < max】，约束从上到下更新并传递。
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isValidBST(TreeNode* root) {
// 根节点没有约束
return isValidBSTTree(root, nullptr, nullptr);
}
// 从上到下验证每个节点是否符合该二叉搜索树的约束【min < root < max】
bool isValidBSTTree(TreeNode* root, TreeNode* min, TreeNode* max){
if(root == nullptr) return true;
// 验证当前节点
if(min != nullptr && min->val >= root->val) return false;
if(max != nullptr && max->val <= root->val) return false;
// 验证左右子树【约束也需要更新】
return isValidBSTTree(root->left, min, root) && isValidBSTTree(root->right, root, max);
}
};
发表于 2022-08-24 11:09:57
回复(0)
使用迭代法进行中序遍历，判断中序遍历的结果是否严格递增。
使用last来记录上一个结点的地址，而不是上一个结点的值。
class Solution { //中序遍历法，迭代
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* last = nullptr;
while (cur || !st.empty()) {
if (cur) {
st.push(cur);
cur = cur->left;
} else {
cur = st.top();
st.pop();
if (last) {
if (cur->val <= last->val)
return false;
}
last = cur;
cur = cur->right;
}
}
return true;
}
};
发表于 2022-06-13 17:46:26
回复(0)
递归思路
非递归方式比较简单，按照中序遍历，然后判断是否有序。
递归
定义一个最小值。如果以当前为根节点的树时BST，那么min就是当前为根节点的树中的最大值。然后再判断min和当前node.val的关系，直接返回false或更新min的值。然后再去判断右子树。说白了和中序遍历思路一样。
private int min = Integer.MIN_VALUE;
public boolean isValidBST (TreeNode root) {
// write code here
if (root == null) return true;
//处理左子树
if (!isValidBST(root.left)) {
return false;
}
//处理当前节点
if (min >= root.val) {
return false;
} else {
min = root.val;
}
//处理右子树
if (!isValidBST(root.right)) {
return false;
}
return true;
}
发表于 2022-04-01 18:03:22
回复(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;
public boolean isValidBST (TreeNode root) {
//左边如何
if(root.left!=null&&!isValidBST(root.left)){
return false;
}
//当前如何
if(pre!=null&&root.val<pre.val){
return false;
}
pre=root;
//右边如何
if(root.right!=null){
return isValidBST(root.right);
}
return true;
}
}
发表于 2022-03-12 15:12:03
回复(0)
刚开始想的先序遍历，每次判断根节点的val是否大于left.val并且小于right.val。但是最后发现这样不行，这样仅仅比较了当前节点的左右子树的根节点，左右子树的其他节点都没有考虑。然后看了别人的思路，递归的时候设置一个区间，当前节点的val得满足在这个区间中
public boolean isValidBST (TreeNode root) {
// write code here
return DFS(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
// 满足 l < root.val< r
public boolean DFS(TreeNode root,int l,int r){
if(root == null)
return true;
if(root.val < l || root.val > r)
return false;
return DFS(root.left,l,root.val) && DFS(root.right,root.val,r);
}
发表于 2022-03-12 11:31:26
回复(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)
2022年408真题也考察类似算法，只不过是使用数组存储二叉树。
注意，并不是左子节点比根节点小，右子节点比根节点大就叫二叉搜索树。可以通过设置一个区间，节点值不在这个区间内，就不是二叉搜索树。
static bool isValidBST_helper(TNode *root, int lower, int upper) {
if (root == NULL)
return true;
int val = root->val;
if (val > upper||val < lower)
return false;
return isValidBST_helper(root->left, lower,val)&&isValidBST_helper(root->right, val,upper);
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* @param root TreeNode类
* @return bool
*/
bool isValidBST(struct TreeNode* root) {
if (root == NULL)
return true;
return isValidBST_helper(root, INT32_MIN+1, INT32_MAX-1);
}
发表于 2023-10-08 19:40:18
回复(1)
中序遍历试试：
class Solution: def inOrderTraversal(self, root: TreeNode) -> List[int]: if root is None: return [] return self.inOrderTraversal(root.left) + [root.val] + self.inOrderTraversal(root.right) def isValidBST(self , root: TreeNode) -> bool: res = self.inOrderTraversal(root) if len(res) <= 1: return True for i in range(len(res)-1): if res[i] >= res[i+1]: return False return True
发表于 2023-03-01 11:55:26
回复(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)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
bool isValidBST(TreeNode* root) {
// 时间复杂度O(N)，空间复杂度O(N)
if (root == nullptr) return true;
if (!isValidBST(root->left) || root->val < pre) return false;
pre = root->val;
return isValidBST(root->right);
}
int pre = INT_MIN;
};
发表于 2022-10-09 17:39:57
回复(0)
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
//二叉收索树的中序遍历是递增的
function inorder(root, arr = []) {
if (root) {
inorder(root.left, arr);
arr.push(root.val);
inorder(root.right, arr);
}
return arr;
}
// function judge(root, flag = "", val = 0) {
// if (root == null || (root.left == null && root.right == null)) return true; //根为null或左右子树都为null
// if (root) {
// //不满足二叉收索树
// if (root.val <= root.left.val || root.val >= root.right.val) return false;
// //满足二叉收索树
// else if (root.val > root.left.val && root.val < root.right.val) {
// if (flag == "left" && root.right.val > val) return false;
// if (flag == "right" && root.left.val < val) return false;
// //判断左右子树是否是二叉收索树
// return (
// judge(root.left, "left", root.val) &&
// judge(root.right, "right", root.val)
// );
// }
// }
// }
function isValidBST(root) {
if (root == null || (root.left == null && root.right == null)) return true;
let inarr = inorder(root);
let temp = [...inarr];
temp.sort((a, b) => a - b);
for (let i = 0; i < inarr.length; i++) {
if (temp[i] != inarr[i]) return false;
}
return true;
}
module.exports = {
isValidBST: isValidBST,
};
发表于 2022-09-29 21:26:01
回复(1)
ArrayList<Integer> list = new ArrayList<>();
public boolean isValidBST (TreeNode root) {
// write code here
ArrayList<Integer> list1 = inorder(root);
int[] ret = new int[list1.size()];
for(int i = 1 ; i < list1.size(); i++){
if(ret[i-1] > ret[i]) return false;
}
return true;
}
ArrayList<Integer> inorder(TreeNode node){
if(node == null) return list;
inorder(node.left);
list.add(node.val);
inorder(node.right);
return list;
}
//佬 救救孩子 孩子用中序遍历 然后判断 为什么不行呀
发表于 2022-09-17 17:24:45
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
//二叉搜索树 按照中序遍历 是有序的
long long pre=INT_MIN;
bool isValidBST(TreeNode* root) {
// write code here
if(root==NULL){
return true;
}
if(!isValidBST(root->left)){
return false;
}
if(pre>root->val){
return false;
}
pre=root->val;
if(!isValidBST(root->right)){
return false;
}
return true;
}
};
发表于 2022-07-10 10:21:55
回复(0)
我的解法感觉比较简单，确定一个节点的左右边界就可以了。
bool isValidBST(TreeNode* root) {
// write code here
return isValidBSTTree(root,INT_MIN,INT_MAX);
}
bool isValidBSTTree(TreeNode* root,int leftVal,int rightVal) {
if(root == NULL){
return true;
}
if(root->val < leftVal || root->val > rightVal){
return false;
}
return isValidBSTTree(root->left,leftVal,root->val) && isValidBSTTree(root->right,root->val,rightVal);
}
bool isValidBST(TreeNode* root) {
// write code here
return isValidBSTTree(root,INT_MIN,INT_MAX);
}
bool isValidBSTTree(TreeNode* root,int leftVal,int rightVal) {
if(root == NULL){
return true;
}
if(root->val < leftVal || root->val > rightVal){
return false;
}
return isValidBSTTree(root->left,leftVal,root->val) && isValidBSTTree(root->right,root->val,rightVal);
}
发表于 2022-05-17 21:09:51
回复(0)
问题信息
难度：
131条回答
627收藏
1932浏览
通过挑战的用户
查看代码-
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号
