simple python O(n) Time and Space Utilizing one Stack with explanation


  • 0
    L
    class Solution(object):
        def verifyPreorder(self, preorder):
            """
            :type preorder: List[int]
            :rtype: bool
            """
            low_bound = float("-inf")
            upper_bound = float("inf")
            n = len(preorder)
            if n < 2:
                return True
            # ele (low_bound,upper_bound,value,left_visited,right_visited)
            stack = []
            stack.append([low_bound, upper_bound, preorder[0], False, False])
            for i in xrange(1, n):
                ele = preorder[i]
                while len(stack) > 0:
                    top = stack[-1]
                    # the ele is the node's child only when
                    # the ele is within the boundary and the corresponding subtree of the node is not visited
                    if (not top[3] and top[0] < ele < top[2]) or (not top[4] and top[2] < ele < top[1]):
                        break
                    else:
                        stack.pop()
                # if stack is empty which means we can't find parent for ele, so return False
                if len(stack) == 0:
                    return False
                top = stack[-1]
                if not top[3] and top[0] < ele < top[2]:
                    stack[-1][3] = True
                    stack.append([top[0], top[2], ele, False, False])
                else:
                    # if the ele is the right child of node, this means left child is None or has been visited,
                    # so assign the left_visited as True
                    stack[-1][3] = True
                    stack[-1][4] = True
                    stack.append([top[2], top[1], ele, False, False])
            return True
    

Log in to reply
 

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