LintCode 95. 验证二叉查找树
题目描述
给定一个二叉树，判断它是否是合法的二叉查找树(BST)
一棵BST定义为：
节点的左子树中的值要严格小于该节点的值。
节点的右子树中的值要严格大于该节点的值。
左右子树也必须是二叉查找树。
一个节点的树也是二叉查找树。
测试样例
输入：{-1}
输出：true
解释：
二叉树如下(仅有一个节点）:
-1
这是二叉查找树。
输入：{2,1,4,#,#,3,5}
输出：true
解释：
二叉树如下：
2
/ \
1 4
/ \
3 5
这是二叉查找树。
解题思路
1、中序遍历
设置一个全局变量pre，用于记录左子树中的最大值。
先获得左子树的处理结果，验证左子树是否是二叉查找树，同时需要判断当前节点是否大于左子树中的最大值pre。
待以上验证完毕，将pre设置为当前节点的值，然后对右子树进行验证。之所以将pre设置为当前节点值是因为要保证右子树中的节点值都要大于当前节点。
2、设置上、下限
分别设置一个上限max_和一个下限min_用来对验证二叉查找树，初始时，上限为sys.maxsize；下限为-sys.maxsize。
先判断当前节点是否处于上、下限之间，然后，对左、右子树递归验证。对于左子树，下限保持为当前节点的下限，上限则更新为当前节点；对于右子树，上限保持为当前节点的上限，下线更新为当前节点。
代码
1、中序遍历
import sys
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if the binary tree is BST, or false
"""
pre = -sys.maxsize
def isValidBST(self, root):
if not root:
return True
# 中序遍历，因此pre代表的是左子树的最右边儿子
if not self.isValidBST(root.left) or root.val <= self.pre:
return False
# 对于右子树来说，pre是就是其父节点
self.pre = root.val
# 当前节点及左子树遍历完毕，接下来遍历右子树
return self.isValidBST(root.right)
2、设置上、下限
import sys
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: The root of binary tree.
@return: True if the binary tree is BST, or false
"""
def isValidBST(self, root):
# 设置上、下限
min_, max_ = -sys.maxsize, sys.maxsize
return self.helper(root, min_, max_)
def helper(self, node, min_, max_):
if not node:
return True
if not min_ < node.val < max_:
return False
# 左子树的下限继承其根节点，上限则为根节点
# 右子树的上限继承其根节点，下限则为根节点
return self.helper(node.left, min_, node.val) and self.helper(node.right, node.val, max_)
