Description
Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.
Example 1:
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?
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
stk = []
last = -inf
for x in preorder:
if x < last:
return False
while stk and stk[-1] < x:
last = stk.pop()
stk.append(x)
return True(code-box)
class Solution {
public boolean verifyPreorder(int[] preorder) {
Deque<Integer> stk = new ArrayDeque<>();
int last = Integer.MIN_VALUE;
for (int x : preorder) {
if (x < last) {
return false;
}
while (!stk.isEmpty() && stk.peek() < x) {
last = stk.poll();
}
stk.push(x);
}
return true;
}
}(code-box)
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
stack<int> stk;
int last = INT_MIN;
for (int x : preorder) {
if (x < last) return false;
while (!stk.empty() && stk.top() < x) {
last = stk.top();
stk.pop();
}
stk.push(x);
}
return true;
}
};(code-box)
func verifyPreorder(preorder []int) bool {
var stk []int
last := math.MinInt32
for _, x := range preorder {
if x < last {
return false
}
for len(stk) > 0 && stk[len(stk)-1] < x {
last = stk[len(stk)-1]
stk = stk[0 : len(stk)-1]
}
stk = append(stk, x)
}
return true
}(code-box)
