Python DFS clear solution


  • 0
    Z

    Follow the definition of BST:

    • every left node's value should be less than the node's and greater than the most recent right nodes'

    • every right node's value should be greater than the node's and less than the most recent left nodes'

    Those max and min values are stored and passed to next recursion.

    class Solution(object):
        def isValidBST(self, root):
            def helper(root, maxval, minval):
                if root:
                    if minval < root.val < maxval:
                            return helper(root.left, root.val, minval) and helper(root.right, maxval, root.val)
                    return False
                return True
            
            if root:
                return helper(root.left, root.val, -sys.maxint) and helper(root.right, sys.maxint, root.val)
            return True
    

Log in to reply
 

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