判断二叉树是否是二叉排序树
二叉排序树又称为二叉排序树，是一种特殊的二叉树结构，它具有以下特点：每个节点的左子树只包含小于当前节点的值，每个节点的右子树只包含大于当前节点的值，而左右子树也分别都是二叉排序树。因此，判断二叉树是否是二叉排序树是程序员面试中非常常见的问题，本文将从多个角度进行分析。
一、递归
判断一棵二叉树是否是二叉排序树的最简单的方法是递归。我们从根节点开始，检查每个节点是否符合二叉排序树的定义，如果符合，则递归检查它的左右子树是不是二叉排序树，直到检查完整棵树。代码示例如下：
```
bool checkBST(TreeNode* root) {
return checkBST(root, LONG_MIN, LONG_MAX);
}
bool checkBST(TreeNode* node, long minVal, long maxVal) {
if (node == nullptr) {
return true;
}
if (node->val <= minVal || node->val >= maxVal) {
return false;
}
return checkBST(node->left, minVal, node->val) && checkBST(node->right, node->val, maxVal);
}
```
其中，minVal和maxVal表示要检查的子树的节点值的取值范围，由于二叉排序树的节点要求，因此左子树的最大值一定小于父节点的值，右子树的最小值一定大于它的值。
二、中序遍历
二叉排序树的中序遍历是升序排列的，因此我们可以对二叉树进行中序遍历，然后判断遍历结果是否升序。具体实现如下：
```
bool checkBST(TreeNode* root) {
stack
TreeNode* pre = nullptr;
while (!s.empty() || root != nullptr) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (pre != nullptr && pre->val >= root->val) {
return false;
}
pre = root;
root = root->right;
}
return true;
}
```
三、广度优先搜索
在二叉树的广度优先搜索中，我们可以按照层次检查每个节点是否符合二叉排序树的定义。代码示例如下：
```
bool checkBST(TreeNode* root) {
queue
q.push({root, {LONG_MIN, LONG_MAX}});
while (!q.empty()) {
auto cur = q.front();
q.pop();
auto node = cur.first;
auto [minVal, maxVal] = cur.second;
if (node == nullptr) {
continue;
}
if (node->val <= minVal || node->val >= maxVal) {
return false;
}
q.push({node->left, {minVal, node->val}});
q.push({node->right, {node->val, maxVal}});
}
return true;
}
```
