# 255 Verify Preorder Sequence in Binary Search Tree

### 255. Verify Preorder Sequence in Binary Search Tree

Medium

      10
/  \
5    12
/ \
2   6

preorder:[10, 5, 2, 6, 12]


O(n) time, O(n) space

class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
stack = []
min_num = -1 << 31  # 初始化最小值为最小整数
for x in preorder:
if x < min_num: # 违反最小值限定则是无效的
return False
while stack and x > stack[-1]: # 将路径中所有小于当前的数pop出来并更新最小值
min_num = stack.pop()
stack.append(x) # 将当前值push进去
return True


O(n) time, O(1) space

we realize that the preorder array can be reused as the stack thus achieve O(1) extra space, since the scanned items of preorder array is always more than or equal to the length of the stack.

class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
# stack = preorder[:i], reuse preorder as stack
min_num = -1 << 31
i = 0
for x in preorder:
if x < min_num:
return False
while i > 0 and x > preorder[i - 1]:
min_num = preorder[i - 1]
i -= 1
preorder[i] = x
i += 1
return True