判断给定的一棵二叉树是否为二叉排序树
时间: 2024-01-14 22:19:56 浏览: 42
以下是判断给定的一棵二叉树是否为二叉排序树的算法:
1.定义一个递归函数,函数名为isBST,参数为root,表示当前子树的根节点。
2.如果当前节点为空,返回True。
3.如果当前节点的左子树不为空,判断左子树上所有节点的值是否小于当前节点的值,如果不是,返回False。
4.如果当前节点的右子树不为空,判断右子树上所有节点的值是否大于当前节点的值,如果不是,返回False。
5.递归判断当前节点的左子树和右子树是否为二叉排序树,如果都是,返回True,否则返回False。
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isBST(root):
if not root:
return True
if root.left and root.left.val >= root.val:
return False
if root.right and root.right.val <= root.val:
return False
return isBST(root.left) and isBST(root.right)
```
相关问题
判别给定二叉树是否为二叉排序树的算法
判断给定二叉树是否为二叉排序树的算法如下:
1. 如果二叉树为空,则返回 true。
2. 如果二叉树不为空,则判断其左子树是否为二叉排序树,如果不是,则返回 false。
3. 判断当前节点是否大于其左子树的最大值,如果不是,则返回 false。
4. 判断当前节点是否小于其右子树的最小值,如果不是,则返回 false。
5. 判断其右子树是否为二叉排序树,如果不是,则返回 false。
6. 如果以上条件都满足,则返回 true。
其中,判断一个二叉树是否为二叉排序树,需要用到中序遍历,即先遍历左子树,再遍历根节点,最后遍历右子树。如果遍历的结果是一个递增的序列,则该二叉树为二叉排序树。
试设计一个判别给定二叉树是否为二叉排序树的算法
以下是判断给定二叉树是否为二叉排序树的算法:
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)
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.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)