Python version based on inorder traversal


  • 20
    G
    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        # @param root, a tree node
        # @return a boolean
        # 7:38
        def isValidBST(self, root):
            output = []
            self.inOrder(root, output)
            
            for i in range(1, len(output)):
                if output[i-1] >= output[i]:
                    return False
    
            return True
    
        def inOrder(self, root, output):
            if root is None:
                return
            
            self.inOrder(root.left, output)
            output.append(root.val)
            self.inOrder(root.right, output)

  • 7
    B

    my solution is like yours, and using sorted and set to validate length and order if correct

    class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
    
        self.res = list()
        self.validation(root)
        
        
        return self.res == sorted(self.res) and len(set(self.res)) == len(self.res)
        
    def validation(self, root):
        
        if not root:
            return 
        else:
            self.validation(root.left)
            self.res.append(root.val)
            self.validation(root.right)

  • 0
    W

    I did almost the same as yours. But my concern is that this solution is quite slow.. Yes, O(n) guaranteed, but do we have chance to "short circuit" as soon as we find the incorrect ordering while doing the inOrder()? I'm just curious why other people getting much better running time than this.


  • 0
    Y

    @WeilanYang
    add a test at the start of inOrder()

    if len(output) > 1 and output[-1] <= output[-2]:
        return
    

  • 0
    M

    Here's a similar solution but with O(1) space, where you only check if the current element is greater than the previous element, and you break out of checking the rest if this is False.

    class Solution(object):
        def isValidBST(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            return self.isBSTHelper(root, [])
            
        def isBSTHelper(self, root, prev=[]):
            if not root:
                return True
            if not self.isBSTHelper(root.left, prev):
                return False
            if not prev:
                prev.append(root.val)
            elif root.val <= prev[0]:
                return False
            prev[0] = root.val
            if not self.isBSTHelper(root.right, prev):
                return False
            return True
    

  • 0

    @yorkshire
    Your suggestion doesn't really improve the solution, because it will travel through the other part of the tree anyway.
    @WeilanYang
    Here is my solution according to your suggestion:

        def isValidBST(self, root):
            self.res = []
            return self.inOrder(root)
            
        def inOrder(self, root):
            if not root: return True
            if not self.inOrder(root.left): return False
            if len(self) and self.res[-1] >= root.val: return False
            self.res.append(root.val)
            return self.inOrder(root.right)

  • 0
    Y

    @lee215 correct my mistake. below version stops traversal and only stores the previous node value not the whole tree

    class Solution(object):
        def isValidBST(self, root):
            self.correct = True
            self.prev = float('-inf')
            self.inorder(root)
            return self.correct
    
        def inorder(self, node):
            if not node or not self.correct:    # return if already found out of order
                return
    
            self.inorder(node.left)
            if node.val <= self.prev:
                self.correct = False
                return          # halt exploration
            self.prev = node.val
            self.inorder(node.right)
    

  • 0
    Y

    My solution, also based on inorder traversal :)

    class Solution(object):
        def isValidBST(self, root):
            if not root:return True
            stack=[]
            res=[]
            while root or stack:
                if root:
                    stack.append(root)
                    root=root.left
                else:
                    root=stack.pop()
                    res.append(root.val)
                    root=root.right
            if res==sorted(res) and len(res)==len(set(res)):
                return True
            else:return False
    

Log in to reply
 

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