255 Verify Preorder Sequence in Binary Search Tree

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

Example 1:

    5
   / \
  2   6
 / \
1   3

Input: preorder = [5,2,1,3,6]
Output: true

Example 2:

Input: preorder = [5,2,6,1,3]
Output: false

Constraints:

  • 1 <= preorder.length <= 104
  • 1 <= preorder[i] <= 104
  • All the elements of preorder are unique.

Follow up: Could you do it using only constant space complexity?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        low = -math.inf
        for num in preorder:
            if num < low:
                return False
            while stack and num > stack[-1]:
                low = stack.pop()
            stack.append(num)
        return True


'''
O(1) space
Use the preoder list as the stack
'''
class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        i = 0
        low = -math.inf
        for num in preorder:
            if num < low:
                return False
            while i > 0 and num > preorder[i - 1]:
                low = preorder[i - 1]
                i -= 1
            preorder[i] = num
            i += 1
        return True