验证二叉搜索树

问题简述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

98. 验证二叉搜索树 - 力扣（LeetCode）

思路

• 判断二叉搜索树的条件：

  • 当前节点的值大于左树的最大值，小于右树的最小值，且左右子树都是二叉搜索树；

Python

# 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: TreeNode) -> bool:

        from dataclasses import dataclass

        @dataclass
        class Info:
            mx: int
            mi: int
            is_bst: bool

        def dfs(x):
            if not x: return Info(float('-inf'), float('inf'), True)

            l, r = dfs(x.left), dfs(x.right)

            mx = max(x.val, r.mx)
            mi = min(x.val, l.mi)
            is_bst = l.is_bst and r.is_bst and l.mx < x.val < r.mi

            return Info(mx, mi, is_bst)

        return dfs(root).is_bst