My 2 python Solutions, with and without INT_MAX and INT_MIN. Both beat about 70%


  • 0
    L

    This is the BFS solution rely on INT_MAX and INT_MIN:

    from collections import deque
    from sys import maxint
    def isValidBST_BFS(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        nodes = deque([(root, maxint, -maxint-1)])
        Flag = True
        while Flag and nodes:
            testnode, maxnum, minnum = nodes.popleft()
            if testnode.left:
                Flag &= testnode.val>testnode.left.val>minnum
                nodes.append((testnode.left, testnode.val, minnum))
            if testnode.right:
                Flag &= testnode.val<testnode.right.val<maxnum
                nodes.append((testnode.right, maxnum, testnode.val))
        return Flag
    

    And here is my in-order traversal solution without INT_MAX and INT_MIN:

    def isValidBST_inOrder(self, root):
        Flag = True
        minFlag = True
        nodes = deque()
        while root or nodes:
            while root:
                nodes.append(root)
                root = root.left
            root = nodes.pop()
            if minFlag:
                maxnum = root.val
                minFlag = False
            elif maxnum>=root.val:
                Flag = False
                break
            else:
                maxnum = root.val
            root = root.right
        return Flag

  • 0
    L

    Just come up with a more concise code for the maxint solution

    def isValidBST_BFS(self, root):
        nodes = deque([(root, maxint, -maxint-1)])
        Flag = True
        while Flag and nodes:
            testnode, maxnum, minnum = nodes.popleft()
            if testnode:
                nodes += (testnode.left, testnode.val, minnum), (testnode.right, maxnum, testnode.val)
                Flag &= maxnum>testnode.val>minnum
        return Flag

Log in to reply
 

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