判断一颗二叉树是否为二叉排序树的完整C代码
时间: 2023-10-19 10:12:26 浏览: 66
以下是判断一棵二叉树是否为二叉排序树的完整C代码:
```c
#include<stdio.h>
#include<stdlib.h>
#include<limits.h> // 引入INT_MIN和INT_MAX
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 判断当前节点是否在指定区间内
bool isValidBSTHelper(struct TreeNode* node, int min, int max) {
if(node == NULL) return true;
if(node->val <= min || node->val >= max) return false;
return isValidBSTHelper(node->left, min, node->val) && isValidBSTHelper(node->right, node->val, max);
}
bool isValidBST(struct TreeNode* root) {
return isValidBSTHelper(root, INT_MIN, INT_MAX);
}
```
其中,isValidBSTHelper函数是递归判断每个节点是否满足二叉排序树的定义,isValidBST函数则是对isValidBSTHelper函数的封装,使得可以从根节点开始判断整棵树是否为二叉排序树。在isValidBSTHelper函数中,min和max参数代表当前节点所在子树中允许的最小值和最大值,如果当前节点的值小于等于最小值或大于等于最大值,则不满足二叉排序树的定义。如果当前节点满足条件,则需要递归判断左右子树是否也满足条件。在isValidBST函数中,将根节点的最小值和最大值设为INT_MIN和INT_MAX,即不做限制,然后调用isValidBSTHelper函数进行判断。