目录
题目
- 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
法一、前序遍历
class Solution:
def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
if root is None:
return True
x = root.val
return left < x < right and \
#递归地验证当前节点的左子树和右子树。对于左子树，下一层递归时，将当前节点的值 x 作为新的右边界，而右子树则将 x 作为新的左边界。如果左子树和右子树都是有效的二叉搜索树，则返回 True；否则返回 False
self.isValidBST(root.left, left, x) and \#递归左子树
self.isValidBST(root.right, x, right)#递归右子树
法二、中序遍历
-
二叉搜索树的中序遍历的结果是一个升序序列，判断当前节点的值是否大于前一个遍历节点的值，满足了说明这个节点是满足二叉搜索树条件的，否则就不满足。
-
由于首个节点没有上一个节点，为了统一计算，初始上一个节点为一个极小值，这样首个节点更新时，其与上一个节点的差值将是一个极大值，从而不会影响最小绝对差的更新
class Solution:
pre = -inf # 上一个遍历的值，初始化为比节点可取的最小值还小的值，保证第一个节点通过
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if root is None: # 空节点，无需处理，返回 True
return True
if self.isValidBST(root.left) is False :#左子树搜索不通过
return False
if root.val <= self.pre:
return False # 前一个节点值大于等于当前值，返回 False
self.pre = root.val # 更新上一个遍历的节点
if self.isValidBST(root.right) is False:#写法等价于if not self.isValidBST(root.right):#先对得到的结果取反，再判断如果是true则进入
return False # 右子树搜索不通过，返回 False
return True
模拟：root = [5,1,4,null,null,3,6]
1.root=5!=none,递归左子树：root=1!=none,递归左子树：为none,return true,判断（true is false)为false不进入；1<=-inf不满足不进入；pre=1;递归右子树：为
none,return true,判断（true is false)为false不进入；最后执行完一遍，return true
2.现在判断完5的左子树为true，5<=1不满足，不进入；pre=5;递归右子树4：4！=none不进入，判断4的左子树：3！=none,判断3的左子树，为none,return ture;3<=5满
足，进入返回False，结束程序
if not语法
if not (...):#先对(...)的结果取反，再判断如果是true则进入
return False
if (...) is False:#对(...)的结果判断如果是False,表示满足if条件则进入
return False
法三、后序遍历
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node: Optional[TreeNode]) -> Tuple:
if node is None:
return inf, -inf
l_min, l_max = dfs(node.left)
r_min, r_max = dfs(node.right)
x = node.val
# 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
if x <= l_max or x >= r_min:
return -inf, inf
return min(l_min, x), max(r_max, x)
return dfs(root)[1] != inf