用C++编写代码,试设计一个判别给定二叉树是否为二叉排序树的算法。
时间: 2024-06-13 15:09:22 浏览: 24
以下是用C++编写的判别给定二叉树是否为二叉排序树的算法:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL),(NULL) {}
};
bool isValidBST(TreeNode* root) {
return isValidBST(root, LONG_MIN, LONG_MAX);
}
bool isValidBST(TreeNode* root, long long lower, long long upper) {
if (root == NULL) {
return true;
}
if (root->val <= lower || root->val >= upper) {
return false;
}
return isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper);
}
```
相关问题
试设计一个判别给定二叉树是否为二叉排序树的算法
以下是判断给定二叉树是否为二叉排序树的算法:
1. 对二叉树进行中序遍历,如果始终能保持前一个值比后一个值小,则说明该二叉树是一棵二叉排序树。
2. 中序遍历时,用一个指针pre指向当前结点的前驱结点,如果pre为空,则说明当前结点是中序遍历的第一个结点,不必判断;否则,如果pre的值小于当前结点的值,则将pre指向当前结点,否则说明该二叉树不是一棵二叉排序树。
以下是判断给定二叉树是否为二叉排序树的Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
self.pre = None
return self.helper(root)
def helper(self, root):
if not root:
return True
if not self.helper(root.left):
return False
if self.pre and self.pre.val >= root.val:
return False
self.pre = root
return self.helper(root.right)
```
试设计一个判别给定二叉树是否为二叉排序树的算法。
以下是判断给定二叉树是否为二叉排序树的算法:
1.定义一个比所有结点值最小值还小的一个值,与结点从小到大做判断即可。
2.如果最小值比判断的值大,则说明不是二叉排序树;如果最小值比判断的值小,则接着往下做判断,直到树的最后一个结点。
3.如果是二叉排序树,则最小值应该是最左侧的值,只要比这个值小。
代码实现如下:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
self.minnum = float('-inf')
return self.inorder(root)
def inorder(self, root: TreeNode) -> bool:
if not root:
return True
if not self.inorder(root.left):
return False
if root.val <= self.minnum:
return False
self.minnum = root.val
return self.inorder(root.right)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)