二叉排序树的判断c++
时间: 2023-12-08 19:39:16 浏览: 44
以下是C++中判断二叉排序树的代码实现:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long minVal, long maxVal) {
if (root == NULL) {
return true;
}
if (root->val <= minVal || root->val >= maxVal) {
return false;
}
return isValidBST(root->left, minVal, root->val) && isValidBST(root->right, root->val, maxVal);
}
int main() {
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(1);
root->right = new TreeNode(4);
root->right->left = new TreeNode(3);
root->right->right = new TreeNode(6);
cout << isValidBST(root) << endl; // 输出:0
return 0;
}
```
其中,isValidBST函数用于判断给定的二叉树是否为二叉排序树。isValidBST函数的第二个重载函数isValidBST(TreeNode* root, long minVal, long maxVal)用于递归判断左右子树是否为二叉排序树,其中minVal和maxVal分别表示左右子树中节点值的最小值和最大值。如果当前节点的值小于等于minVal或大于等于maxVal,则返回false,否则递归判断左右子树是否为二叉排序树。