Time: 2019-08-10
题目描述
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
按照BST的特征来进行筛选过滤。注意BST是当前结点要比全部的左子树的元素要大，比全部的右子树的元素要小，所以上下边界并不是临近结点。
代码
标准的模板写法：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
return self.dfs(root)
def dfs(self, node, lower=float('-inf'), upper=float('inf')):
# 递归出口
if not node:
return True
val = node.val
# 若当前结点值小于等于左边界或者大于等于右边界，则不是BST
if val <= lower or val >= upper:
return False
# 递归拆解
# 向右子树，则当前结点值是下界
if not self.dfs(node.right, val, upper):
return False
# 向左子树，当前结点值是上界
if not self.dfs(node.left, lower, val):
return False
return True
时空复杂度
时间复杂度：O(n)
相似题目
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/
END.
