• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

Consider the following binary search tree:

     5
/ \
2   6
/ \
1   3


Example 1:

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


Example 2:

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


## Code

class Solution {
public boolean verifyPreorder(int[] preorder) {
if(preorder == null || preorder.length == 0) return true;
Stack<Integer> s = new Stack<>();

int min = Integer.MIN_VALUE;

for(int num : preorder) {
if(num < min){
return false;
}

while(!s.isEmpty() && s.peek() < num) {
min = s.pop();
}

s.push(num);
}

return true;
}
}

class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stack = []
min = float("-inf")

for num in preorder:
# 当前的min是之后点的最小值，所以不能出现num < min
if num < min:
return False

# 如果num < stack.peek()说明当前还在左子树
# 当num > stack.peek()时，说明已经到了右子树了
# 此时需要找到当前点是哪个点的右子树，并且修改min，同时pop出stack中的值
while len(stack) != 0 and num > stack[-1]:
min = stack.pop()

stack.append(num)

return True