Python Iterative and Recursive Solutions


  • 0
    F
    1. Iterative, using inorder traversal idea
    class Solution(object):
       
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            stack, rst = [], []
            while stack or root:
                if root:
                    stack.append(root)
                    root = root.left
                else:
                    node = stack.pop()
                    if rst and node.val <= rst[-1]:
                        return False
                    rst.append(node.val)
                    root = node.right
            return True
    
    1. Recursive
    class Solution(object):
       
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def helper(root, minV, maxV):
                if not root: return True
                if root.val <= minV or root.val >= maxV:
                    return False
                return helper(root.left, minV, root.val) and helper(root.right, root.val, maxV)
            return helper(root, float('-inf'), float('inf'))
    
    
    
    
    )

  • 0
    N

    I have pretty much the same recursive approach:

    class Solution(object):
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            def _is_bst(node, lower, upper):
                if not node:
                    return True
                
                is_within_range = ((lower is None or lower < node.val) and
                                   (upper is None or upper > node.val))
                if not is_within_range:
                    return False
                
                return (_is_bst(node.left, lower, node.val) and
                        _is_bst(node.right, node.val, upper))
                        
            if not root:
                return True
                
            return _is_bst(root, None, None)
    

Log in to reply
 

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