试设计一个判别给定二叉树是否为二叉排序树的算法。
时间: 2024-01-14 07:19:55 浏览: 83
写一算法,判断一棵二叉树是否是一棵二叉排序树。
以下是判断给定二叉树是否为二叉排序树的算法:
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)
```
阅读全文