输入一棵树，判断这棵树是否为二叉搜索树。首先要知道什么是排序二叉树，二叉排序树是这样定义的，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点
#方法1，直接判断
直接判断的关键在于不能只是单纯地判断根、左、右三个节点的大小关系，左子树的右节点不仅要大于父节点，还要小于父节点的父节点，右子树的左节点不仅要小于父节点，还要大于父节点的父节点。判断代码如下。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None class Solution:
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True def isBSTHelper(node, lower_limit, upper_limit):
#节点值应大于下限，小于上限
if lower_limit is not None and node.val <= lower_limit:
return False
if upper_limit is not None and upper_limit <= node.val:
return False #随着向下遍历，对于左子树，被不断更新的是上限值（必须小于其父节点），对于右子树，被不断更新的是下限值（必须大于其父节点）
left = isBSTHelper(node.left, lower_limit, node.val) if node.left else True
if left:
right = isBSTHelper(node.right, node.val, upper_limit) if node.right else True
return right
else:
return False return isBSTHelper(root, None, None)
#2 利用中序遍历
根据二叉排序树的特点，按照中序遍历的顺序，应当符合当前遍历到的节点值大于前一个遍历到的节点值，即中序遍历序列是一个有序序列，可以直接对中序遍历得到的序列进行判断，也可以在遍历的过程中进行判断。第二种方法的判断代码如下
def isbst(self,node):
global lastvalue
lastvalue=float('-inf') #遍历的前一个节点的值
def isbst2(node):
global lastvalue
if node==None:
return True
if isbst2(node.left) is not True:
return False
if node.val<lastvalue:
return False
lastvalue=node.val#更新
if isbst2(node.right) is not True:
return False
return True
return isbst2(node)