给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。
例：
图1
图2
数据范围：节点数量满足 
，节点上的值满足 
[编程题]判断是不是二叉搜索树
超级好理解的思路！具体就是：如果这个树是二叉搜索树，那么这个二叉搜索树的中序遍历就是递增的！那么解决方法很简单，先中序遍历这个树，然后再判断遍历得到的数组是不是升序的，如果不是，就返回false；如果是就返回true；
void judge(struct TreeNode *Node , int **std , int **nums){
if (Node != NULL) {
(**nums) ++;
judge(Node->left , std , nums);
(**std) = Node->val;
(*std) ++;
judge(Node->right , std , nums);
}
}
bool isValidBST(struct TreeNode* root ) {
// write code here
struct TreeNode * head=root;
int std[10000];
int *p = &std[0];
int nums = 0;
int *q = &nums;
judge(head , &p , &q);
for (int i = 0; i<nums-1; i++) {
if (std[i] > std[i+1]) {
return false;
}
}
return true;
}
发表于 2025-03-18 19:25:45
回复(0)
#include <stdbool.h>
#include <limits.h>
bool isValidBSTHelper(struct TreeNode* root, long min, long max) {
if (root == NULL) {
return true;
}
if (root->val <= min || root->val >= max) {
return false;
}
return isValidBSTHelper(root->left, min, root->val) && isValidBSTHelper(root->right, root->val, max);
}
bool isValidBST(struct TreeNode* root) {
return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}
编辑于 2024-03-31 15:49:22
回复(0)
bool isValidBSTMaxMin(struct TreeNode* root , int *Min, int *Max) {
int LeftMin, LeftMax, RightMin, RightMax;
bool LeftReturn, rightRturn;
if(root==NULL)
return true;
*Min = root->val;
*Max = root->val;
if(root->left!=NULL) {
LeftReturn=isValidBSTMaxMin(root->left, &LeftMin, &LeftMax);
*Min = LeftMin > *Min ? *Min : LeftMin;
*Max = LeftMax > *Max ? LeftMax : *Max;
}
if(root->right!=NULL) {
rightRturn=isValidBSTMaxMin(root->right, &RightMin, &RightMax);
*Min = RightMin > *Min ? *Min : RightMin;
*Max = RightMax > *Max ? RightMax : *Max;
}
if(root->left!=NULL)
if((LeftReturn==false) || (LeftMax >= root->val))
return false;
if(root->right!=NULL)
if((rightRturn==false) || (RightMin <= root->val))
return false;
return true;
}
bool isValidBST(struct TreeNode* root ) {
int Min, Max;
return isValidBSTMaxMin(root, &Min, &Max);
}
编辑于 2024-03-16 18:21:14
回复(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)
有点笨的办法
左子树找最大值
右子树找最小值
然后比对
#include <stdbool.h>
struct TreeNode* tree(struct TreeNode* root,int flag){
if(root == NULL){
return NULL;
}
struct TreeNode* left = NULL;
struct TreeNode* right= NULL;
if(root->left!=NULL){
if(root->left->val>root->val){
return NULL;
}
left = tree(root->left,1);
if(left==NULL){
return NULL;
}
if(left->val>root->val){
return NULL;
}
}
if(root->right!=NULL){
if(root->right->val<root->val){
return NULL;
}
right = tree(root->right,0);
if(right==NULL){
return NULL;
}
if(right->val<root->val){
return NULL;
}
}
if(flag!=2&&left==NULL&&right==NULL){
return root;
}
if(flag == 0&&left!=NULL){
return left;
}if(flag==1&&right!=NULL){
return right;
}
return root;
}
bool isValidBST(struct TreeNode* root ) {
if(root==NULL){
return true;
}
else if(tree(root,2)==NULL){
return false;
}
return true;
}
发表于 2023-09-22 17:27:43
回复(0)
bool isValidBST(struct TreeNode* root )
{
// write code here
static struct TreeNode*f=NULL;
if(root)
{
bool h=true;
bool l;
bool r;
l=isValidBST(root->left);
if(false==l)
{
return false;
}
if(f)
{
if(f->val<root->val)
{
h=true;
}
else
{
h=false;
}
}
f=root;
if(h)
{
isValidBST(root->right);
}
else
{
return false;
}
}
return true;
}
发表于 2023-06-29 10:46:24
回复(0)
int max = 0;
bool turn = false;
bool check(struct TreeNode* root){
if(!root) return true;
bool a = check(root->left);
if(!turn)
turn = true, max = root->val;
else
if(root->val < max)
return false;
else
max = root->val;
bool b = check(root->right);
return a&&b;
}
bool isValidBST(struct TreeNode* root ) {
// write code here
return check(root);
}
设置一个变量记录第一次到达中序遍历的第一个结点，以第一个结点的值作为max的初值，此后遍历的节点值只能大于之前的最大值，不能小于；如果小于就返回false
发表于 2022-10-11 20:06:05
回复(0)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
#include <stdbool.h>
static int i=0;
void traverse(struct TreeNode* root, int *arr){
if(root==NULL){
return;
}
traverse(root->left,arr);
arr[i++]=root->val;
traverse(root->right,arr);
}
int treeSize(struct TreeNode*root){
if(root==NULL){
return 0;
}
return treeSize(root->left)+treeSize(root->right)+1;
}
bool isValidBST(struct TreeNode* root ) {
// write code here
int count=treeSize(root);
int *arr=(int*)malloc(count*sizeof(int));
traverse(root,arr);
for(int k=0; k<count-1; k++){
if(arr[k]>arr[k+1])
return false;
}
return true;
}
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
#include <stdbool.h>
static int i=0;
void traverse(struct TreeNode* root, int *arr){
if(root==NULL){
return;
}
traverse(root->left,arr);
arr[i++]=root->val;
traverse(root->right,arr);
}
int treeSize(struct TreeNode*root){
if(root==NULL){
return 0;
}
return treeSize(root->left)+treeSize(root->right)+1;
}
bool isValidBST(struct TreeNode* root ) {
// write code here
int count=treeSize(root);
int *arr=(int*)malloc(count*sizeof(int));
traverse(root,arr);
for(int k=0; k<count-1; k++){
if(arr[k]>arr[k+1])
return false;
}
return true;
}
发表于 2022-07-01 17:04:28
回复(0)
问题信息
难度：
11条回答
888收藏
5436浏览
通过挑战的用户
查看代码-
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号
