试写一个判别给定二叉树是否为二叉排序树的
时间: 2024-06-18 21:06:12 浏览: 165
判断一棵二叉树是否为二叉排序树,可以通过中序遍历的方式来实现。具体实现步骤如下:
1. 从二叉树的根节点开始,递归遍历左子树;
2. 记录下当前节点的值,如果当前节点的值小于等于上一个节点的值,则返回 false;
3. 递归遍历右子树,并将右子树中的节点值与当前节点值进行比较,如果右子树中存在节点值小于等于当前节点值,则返回 false;
4. 如果整个遍历过程没有返回 false,则返回 true。
下面是一个示例代码,具体实现可能会有所不同,但思路大致相同:
```python
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
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)
```
阅读全文