判断一棵树是否为二叉排序树
时间: 2023-09-29 11:03:29 浏览: 88
判断一棵树是否为二叉排序树,可以采用中序遍历的方法。若中序遍历得到的节点序列为升序,则该树为二叉排序树;反之,不是二叉排序树。我们可以通过递归实现中序遍历算法,具体过程如下:
1.若树为空,返回true;
2.中序遍历左子树;
3.判断当前节点值是否大于前一个节点值;
4.递归遍历右子树;
5.若遍历完整个树都没有发现错误,则返回true。
下面是一份使用Python实现的代码示例,可以作为参考:
```
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def isBST(self, root):
self.prev = None
return self.isValidBST(root)
def isValidBST(self, root):
if not root:
return True
if not self.isValidBST(root.left):
return False
if self.prev and self.prev.val >= root.val:
return False
self.prev = root
return self.isValidBST(root.right)
```
请注意,该代码仅仅是一种实现方式,由于不知道您的实际需求,建议更根据实际情况编写代码。