【LeetCode】Hot100:验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

英文题目
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtreeof 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.

解题思路

画了一个四层的二叉树，发现递归方法是，左子树的最右节点应该比根节点小，右子树的最左节点应该比根节点大，基于此写的代码（事实上只要想着所有点，然后更新边界，就可以不用重复遍历来递归了）

AC代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def judge(root):if root.left is None and root.right is None:return Trueif root is None:return Trueleft, right, leftflag, rightflag = root.left, root.right, True, Trueif left is not None:while left.right is not None:left = left.rightleftflag = root.val > left.val and judge(root.left)if right is not None:while right.left is not None:right = right.leftrightflag = root.val < right.val and judge(root.right)return  leftflag and rightflagreturn judge(root)

官方题解

想到使用边界后面思路就一下子通了

class Solution:def isValidBST(self, root: TreeNode) -> bool:stack, inorder = [], float('-inf')while stack or root:while root:stack.append(root)root = root.leftroot = stack.pop()# 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树if root.val <= inorder:return Falseinorder = root.valroot = root.rightreturn True