03.验证二叉搜索树(98)

Python示例

核心是通过全部变量 pre 记录前节点的值

class Solution:
    pre = float('-inf')
    def isValidBST(self, root: TreeNode) -> bool:
        if not root: return True
        if not self.isValidBST(root.left):  # 如果左子树不符合，就返回否
            return False
        if root.val <= self.pre:  # 比前面的小，或者相等
            return False 
        self.pre = root.val 
        if not self.isValidBST(root.right):
            return False
        
        return True

本质上就是 中序遍历，下面改成中序遍历的版本。

class Solution:
    res = True 
    pre = float('-inf')
    def isValidBST(self, root: TreeNode) -> bool:
        def midorder(root):
            if not self.res: return 
            if not root: return 
            
            midorder(root.left)
            if root.val <= self.pre:
                self.res = False 
            self.pre = root.val 

            midorder(root.right)
        if not root: return self.res 
        midorder(root)
        return self.res