Verify Preorder Sequence in Binary Search Tree
Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.
You may assume each number in the sequence is unique.
Follow up: Could you do it using only constant space complexity?
URL: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
import sys
class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
stack = []
root = -sys.maxsize-1
for entries in preorder:
if entries < root:
return False
while stack != [] and stack[-1] < entries:
root = stack.pop()
stack.append(entries)
return True