本文共 2200 字，大约阅读时间需要 7 分钟。
leetcode 98 Validate Binary Search Tree 题目描述： Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: 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. Example 1: 2 / \ 1 3 Binary tree [2,1,3], return true. Example 2: 1 / \ 2 3 Binary tree [1,2,3], return false. 分析： 中序遍历，比较当前节点的值是否大于前一个节点的值，若始终满足大于，则返回真，否则返回假。 法一，需要额外的O(n)的空间Python代码：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ if root is None: return True if root.left==None and root.right==None: return True self.List=[] self.left_root_right(root) #调用left_root_right()函数，中序遍历二叉搜索树，将节点的值存入列表List中 for i in range(1,len(self.List)): if self.List[i]<=self.List[i-1]: #通过for循环遍历列表，若当前值少于或等于前一个值，则返回False return False return True def left_root_right(self,root): if root==None: return self.left_root_right(root.left) #中序遍历当前子树的左子树 self.List.append(root.val) #将当前子树的根节点的值存入列表List中 self.left_root_right(root.right)#中序遍历当前子树的右子树
法二，不需要额外的O(n)空间
Python代码：
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): pre=None '''为Solution类添加pre数据成员，在中序遍历二叉搜索树的过程中，pre用来指向当前节点的前驱节点。 注意：pre不能放在isValidBST函数的内部。如果将pre放在isValidBST函数的内部，则每一次递归调用isValidBST函数的时候， pre都将重新赋值为None。实际上，在每一次递归调用时，我们需要的是上一次调用结束时pre的值''' def isValidBST(self, root): """ :type root: TreeNode :rtype: bool """ if root is None: return True Bool= self.isValidBST(root.left) if self.pre!=None: Bool=Bool and (self.pre.val
转载地址：http://mdyai.baihongyu.com/