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 <= 1041 <= 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
|