方法1
中序遍历,验证
二叉搜索树条件:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
故我们可以先进行中序遍历,先遍历左子树，当到达叶节点时，记录该结点，然后记录其父节点，然后是右节点.然后验证即可
output = []维持一个数组储存节点的值
self.inOrder(root, output)中序遍历
for i in range(1, len(output)):
if output[i-1] >= output[i]:
return False
return True
对数组进行验证,看是否满足二叉搜索树的条件
方法2
直接遍历比较
初始化两个参数lessThan = float('inf'), largerThan = float('-inf')
def isValidBST(self, root, lessThan = float('inf'), largerThan = float('-inf')):
if not root:
return True
if root.val <= largerThan or root.val >= lessThan:
return False
return self.isValidBST(root.left, min(lessThan, root.val), largerThan) and \
self.isValidBST(root.right, lessThan, max(root.val, largerThan))
从根节点同时向左子树和右子树遍历,lessThan和largerThan一直为父节点的值,若不满足条件,则说明不符合二叉搜索树.
