Java

blue&&lan

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)

Java

小灰灰QAQ

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)

C++

QNBZ

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;
}
};

发表于 2021-12-21 07:45:10 回复(0)

Java

滴滴打🐷

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)

C++

牛客757388365号

使用迭代法进行中序遍历，判断中序遍历的结果是否严格递增。

使用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)

Java

王小汪

递归思路

非递归方式比较简单，按照中序遍历，然后判断是否有序。

递归

定义一个最小值。如果以当前为根节点的树时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)

C++

整顿职场的外卷侠很年轻

前序遍历验证每个节点是否符合该二叉搜索树的约束【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)

Java

薛阿牛

交了好几次终于过了。。。

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)

Java

可有可无q

刚开始想的先序遍历，每次判断根节点的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)

Python3

Namely

中序遍历试试：

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)

Java

键盘都敲坏了.

递归实现。定义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)

Java

不会起名就这样吧

搜索二叉树中序遍历为递增的，中序遍历后判断是否递增即可

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)

Java

pein531

检查中序遍历是否满足单调递增的性质就可以了，用一个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)

C++

wjm_lzy

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isValidBST(TreeNode* root) {
        // write code here
        //使用递归思想，如果一棵树的左子树最大值小于根，并且根小于右子树最小值，对于每个点这样判断即可
        //中序遍历，左根右排序上升的，那么我们需要有一个指针指向前一个结点
        if(root == nullptr) return false;
        bool Pleft = true;
        bool Pright = true;
        if(root->left!=nullptr) Pleft = isValidBST(root->left);
        if(pre == nullptr){
            pre = root;
        }
        else{
            if(pre->val>=root->val){
                return false;
            }
            pre = root;
        }
        if(root->right!=nullptr) Pright = isValidBST(root->right);
        return Pleft&&Pright;
    }
    TreeNode * pre = nullptr;
};

发表于 2025-04-19 18:12:41 回复(0)

Go

PeterLee6688

var Min = (int)(^uint(0) >> 1)/-1
func isValidBST(root *TreeNode) bool {
	// write code here
	if root == nil {
		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
}

发表于 2024-05-19 21:34:06 回复(0)

C

牛客865647821号

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)

Java

小杨yyy

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)

C++

Spectre_

/**
 * 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)

Javascript

wuster6016

/*

* 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)

判断是不是二叉搜索树

输入

输出

说明

输入

输出

说明

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

递归思路

迭代版中序遍历

Morris遍历版中序遍历

问题信息

热门推荐

通过挑战的用户

相关试题