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?
A:
每次找到小于的， 然后分开查询
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
return helper(preorder, 0, preorder.size()-1);
}
private:
bool helper(vector<int>& preorder, int start, int end){
if(start >= end) // just one value
return true;
int val = preorder[start];
int mid = start+1; // mid point to first position either go-beyond, or with bigger value
while(mid<=end && preorder[mid] < val){
mid++;
}
for(int i = mid; i<=end;i++){
if(preorder[i] < val )
return false;
}
return helper(preorder, start+1,mid-1) && helper(preorder, mid, end);
}
};
上面这个方法，说都通过了，可是有点儿慢。 修改下，加上范围. 这样，可以省掉上面的for循环
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
return helper(preorder, 0, preorder.size()-1, INT_MIN, INT_MAX);
}
private:
bool helper(vector<int>& preorder, int start, int end, int lower, int upper){
if(start > end) // just one value
return true;
int val = preorder[start];
if(val <=lower || val >= upper)
return false;
if(start == end)
return true;
int mid = start+1; // mid point to first position either go-beyond, or with bigger value
while(mid<=end && preorder[mid] < val){
if(preorder[mid]<=lower)
return false;
mid++;
}
return helper(preorder, start+1,mid-1, lower, val) && helper(preorder, mid, end, val, upper);
}
};
这次通过了， 可是，只是faster than 5.65%
观察得知，我们还是有了个while 循环，考虑去掉。 用stack 来表示。
This problem is very interesting. Recursive approach is very
straightforward, though solution is likely of O(nlogn)/O(logn)
time/space complexity (avg), or O(N^2)/O(N) worst case.
The key to optimize is to recall how iterative(non-recursive)
pre-order traversal works, then follow the same idea to "reconstruct"
BST from preorder sequence, during which we need a stack to keep track
of node path from root. The trick here is to use input preorder sequence
to simulate the stack in-place. For verification purpose, we need to
maintain a "lower bound" variable: when we visit a node that is the
right child of its parent, the parent's value must be lower bound of all
subsequent values.
class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
stack<int> st;
int lower_bound = INT_MIN;
for(int i = 0;i< preorder.size();i++){
int v = preorder[i];
if(v <= lower_bound) // check that it's in the range
return false;
if(st.empty() || v < st.top()){
st.push(v);
}else{
lower_bound = st.top();
st.pop();
i--; // this is the KEY, step back so we can check with grandparent
}
}
return true;
}
};
Mistakes:
