[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: Optional[TreeNode]) -> bool:

        def dfs(root):
            if not root:
                return True
            else: 
                left = dfs(root.left)
                if root.val > self.last:
                    self.last = root.val
                else:
                    return False
                right = dfs(root.right)
            return left and right

        self.last = -float('inf')
        return dfs(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:

        if not root:
            return True

        stack = []
        res = []
        current = root
        last = None

        while stack or current:
            while current:
                stack.append(current)
                current = current.left
            
            t = stack.pop(-1)

            if last and last.val >= t.val:
                return False
            else:
                last = t

            res.append(t.val)
            current = t.right
        return True