Python two approaches


  • 0
    D

    a) serialize BST and validate it's sorted in ascending order

    class Solution(object):
        def isValidBST(self, root):
            serialized = []
            self.inorder(root, serialized)
            for i in range(1, len(serialized)):
                if serialized[i-1] >= serialized[i]:
                    return False
            return True
    
        def inorder(self, root, res):
            if not root:
                return
            self.inorder(root.left, res)
            res.append(root.val)
            self.inorder(root.right, res)
    

    b) validate in-place

    class Solution(object):
        def isValidBST(self, root):
            return self.isvalid(root, float('-inf'), float('inf'))
        
        def isvalid(self, root, low, high):
            if not root:
                return True
            if root.val <= low or root.val >= high:
                return False
            return self.isvalid(root.left, low, root.val) and self.isvalid(root.right, root.val, high)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.