2、试设计一个判别给定二叉树是否为二叉排序树的算法
时间: 2024-01-14 11:19:55 浏览: 26
以下是判断给定二叉树是否为二叉排序树的算法:
1. 对于空树,返回True。
2. 对于非空树,递归判断左右子树是否为二叉排序树。
3. 判断当前节点的值是否大于左子树中的最大值,小于右子树中的最小值,如果满足则返回True,否则返回False。
```python
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. 对二叉树进行中序遍历,如果始终能保持前一个值比后一个值小,则说明该二叉树是一棵二叉排序树。
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)
```