# 255. 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.

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
``````

Could you do it using only constant space complexity?

``````     5
/ \
2   6
/ \
1   3
``````

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN;
stack<int> s;
for (auto a : preorder) {
if (a < low) return false;
while (!s.empty() && a > s.top()) {
low = s.top(); s.pop();
}
s.push(a);
}
return true;
}
};
``````

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN, i = -1;
for (auto a : preorder) {
if (a < low) return false;
while (i >= 0 && a > preorder[i]) {
low = preorder[i--];
}
preorder[++i] = a;
}
return true;
}
};
``````

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
return helper(preorder, 0, preorder.size() - 1, INT_MIN, INT_MAX);
}
bool helper(vector<int>& preorder, int start, int end, int lower, int upper) {
if (start > end) return true;
int val = preorder[start], i = 0;
if (val <= lower || val >= upper) return false;
for (i = start + 1; i <= end; ++i) {
if (preorder[i] >= val) break;
}
return helper(preorder, start + 1, i - 1, lower, val) && helper(preorder, i, end, val, upper);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/255

Binary Tree Preorder Traversal

Validate Binary Search Tree

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/discuss/68142/Java-O(n)-and-O(1)-extra-space

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation