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 <= 104
1 <= preorder[i] <= 104
- All the elements of
preorder
are unique.
Follow up: Could you do it using only constant space complexity?
Companies:
VMware
Related Topics:
Stack, Tree, Binary Search Tree, Recursion, Monotonic Stack, Binary Tree
Similar Questions:
// OJ: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
bool verifyPreorder(vector<int>& A) {
stack<int> s;
int mn = INT_MIN;
for (int n : A) {
if (n < mn) return false;
while (s.size() && s.top() < n) {
mn = s.top();
s.pop();
}
s.push(n);
}
return true;
}
};
Or if we are allowed to change the input array to simulate the stack
// OJ: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1) if we don't count the space used by the input array.
class Solution {
public:
bool verifyPreorder(vector<int>& A) {
int mn = INT_MIN, j = -1;
for (int i = 0; i < A.size(); ++i) {
if (A[i] < mn) return false;
while (j >= 0 && A[j] < A[i]) mn = A[j--];
A[++j] = A[i];
}
return true;
}
};