问题描述

https://leetcode.cn/problems/validate-binary-search-tree/description/

解题思路

二叉搜索树的性质是：root节点要大于左子树的最大值，小于右子树的最小值。

同时，对上层，也要更新本层的最大值和最小值以供继续递归。

代码

# 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:
        flag = True
        def dfs(root):
            if root is None:
                return None, None
            left_min, left_max = dfs(root.left)
            right_min, right_max = dfs(root.right)
            nonlocal flag
            if not flag:
                return None, None
            mins, maxs = root.val, root.val
            if left_max and left_max < root.val:
                mins = left_max
            elif left_max:
                flag = False
            if right_min and right_min > root.val:
                maxs = right_min
            elif right_min:
                flag = False
            if left_min:
                mins = min(left_min, mins)
            if right_max:
                maxs = max(maxs, right_max)
            return mins, maxs
        dfs(root)
        return flag