判别给定二叉树是否为二叉排序树的算法
时间: 2023-04-24 14:06:05 浏览: 78
判断给定二叉树是否为二叉排序树的算法如下:
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)
```
设计一个判别给定二叉树是否为二叉排序树的算法
以下是判断给定二叉树是否为二叉排序树的算法实现:
1.中序遍历法
```python
def is_bst(root):
def inorder(node):
nonlocal prev
if not node:
return True
if not inorder(node.left):
return False
if prev and prev.val >= node.val:
return False
prev = node
return inorder(node.right)
prev = None
return inorder(root)
```
2.递归法
```python
def is_bst(root):
def helper(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True
val = node.val
if val <= lower or val >= upper:
return False
if not helper(node.right, val, upper):
return False
if not helper(node.left, lower, val):
return False
return True
return helper(root)
```