Python three lines recursive DFS, and iterative DFS


  • 0
    A

    Recursive:

    class Solution(object):
        def isValidBST(self, root):
            return self.helper(root,-float('inf'),float('inf'))
            
        def helper(self,root,lb,rb):
            
            if not root: return True
            return (lb < root.val < rb ) and self.helper(root.left,lb,root.val) and self.helper(root.right,root.val,rb)
            
    

    Iterative:

    class Solution(object):
        def isValidBST(self, root):
            return self.helper(root,-float('inf'),float('inf'))
        
        
        def helper(self,root,lb,rb):
            
            if not root: return True
            stack = [(root,lb,rb)]
            while stack:   
                node, lv, rv = stack.pop()
                if node.val<= lv or node.val >=rv:
                    return False
                if node.right:
                    stack.append((node.right,node.val,rv))
                if node.left:
                    stack.append((node.left,lv,node.val)) 
            
            return True
                
            
    

Log in to reply
 

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