判断二叉树是否为二叉排序树
时间: 2023-10-19 14:19:58 浏览: 52
判断一棵二叉树是否为二叉排序树,需要满足以下条件:
1. 左子树中所有节点的值都小于根节点的值;
2. 右子树中所有节点的值都大于根节点的值;
3. 左子树和右子树都是二叉排序树。
可以采用递归的方式进行判断,具体实现可以参考下面的代码:
```
bool isBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if (root == NULL) {
return true;
}
if (minNode != NULL && root->val <= minNode->val) {
return false;
}
if (maxNode != NULL && root->val >= maxNode->val) {
return false;
}
return isBST(root->left, minNode, root) && isBST(root->right, root, maxNode);
}
bool isBinarySearchTree(TreeNode* root) {
return isBST(root, NULL, NULL);
}
```
其中,minNode 和 maxNode 分别代表左子树和右子树中节点值的范围。初始时,minNode 和 maxNode 都为 NULL,代表没有限制。在递归过程中,更新 minNode 和 maxNode 的值,用于对左子树和右子树的值进行限制。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)