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 Follow up: Could you do it using only constant space complexity?
// 44ms, 60%
class Solution {
private:
int check(const vector<int>& preorder, int minv, int maxv, int left) {
if (left >= preorder.size() || preorder[left] < minv || preorder[left] > maxv)
return left;
int r = check(preorder, minv, preorder[left], left + 1);
return check(preorder, preorder[left], maxv, r);
}
public:
bool verifyPreorder(vector<int>& preorder) {
return check(preorder, INT_MIN, INT_MAX, 0) == preorder.size();
}
};
// 584ms, 16%
class Solution {
private:
bool check(const vector<int>& preorder, int b, int e, optional<int> min_value) {
if (b > e || b >= preorder.size())
return true;
if (min_value.has_value() && preorder[b] < min_value.value())
return false;
if (b == e) {
return true;
}
int i = b + 1;
while (i <= e && preorder[i] < preorder[b]) {
if (min_value.has_value() && preorder[i] < min_value.value())
return false;
i++;
}
if (!check(preorder, b + 1, i - 1, min_value))
return false;
return check(preorder, i, e, preorder[b]);
}
public:
bool verifyPreorder(vector<int>& preorder) {
return check(preorder, 0, preorder.size()-1, optional<int>());
}
};