My AC Python codes


  • 0
    H

    At first, I validate the tree directly based on the definition of a BST (each node is bigger than its left sub-tree and smaller than its right sub-tree). So I just traverse the tree and check every node.

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def check(r, val, left):
                if r == None:   
                    return True
                if left and r.val >= val:
                    return False
                elif not left and r.val <= val:
                    return False
                return check(r.left, val, left) and check(r.right, val, left)
            
            def traverse(r):
                if r == None:   return True
                if not (check(r.left, r.val, True) and check(r.right, r.val, False)): return False
                return traverse(r.left) and traverse(r.right)
            
            return traverse(root)
    

    Actually, we can also validate the condition that each node is larger than previously visited node. So we can apply inorder traversal while recording a 'pre' node. Following is a recursive implementation.

    class Solution(object):
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            self.pre = ListNode(-2**32)
            def inorder(r):
                if r == None:   
                    return True
                a = inorder(r.left)
                if r.val <= self.pre.val:
                    return False
                self.pre = r
                b = inorder(r.right)
                return a and b 
            
            return inorder(root)
    

    And this is a iterative implementation.

    class Solution(object):
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            pre = ListNode(-2**32)
            node, stack = root, []
            while node!=None or stack:
                while node != None:   
                    stack.append(node)
                    node = node.left
                node = stack.pop()
                if node.val <= pre.val:
                    return False
                pre = node
                node = node.right
            
            return True
    

Log in to reply
 

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