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.
Follow up:
Could you do it using only constant space complexity?
Could you do it using only constant space complexity?
Answer:
1. Recursion: O(n*logn) time, Space:O(n)!
public boolean verifyPreorder(int[] preorder) {
return verify(preorder, 0, preorder.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
//Recursive in array range [start, end]
//Verify root in the [min, max], then recursive in left subtree and right subtree!
private boolean verify(int[] preorder, int start, int end, int min, int max) {
//tricky!!!
if (start > end) {
return true;
}
int root = preorder[start];
if (root > max || root < min) {
return false;
}
int rightIndex = start;
//find the first element > root; if non, return end+1!
while (rightIndex <= end && preorder[rightIndex] <= root) {
rightIndex++;
}
return verify(preorder, start + 1, rightIndex - 1, min, root) && verify(preorder, rightIndex, end, root, max);
}
2. Iteratively using stack! Time : O(n), Space:O(n)
public boolean verifyPreorder(int[] preorder) {
Stack<Integer> stack = new Stack<Integer>();
int lastSmallerRoot = Integer.MIN_VALUE;
for(int i=0; i<preorder.length; i++){
int t = preorder[i];
if(stack.isEmpty() || t < stack.peek()){
if(t > lastSmallerRoot){
stack.push(t);
}else{
//current element > most closest smaller root assumed!
return false;
}
}else{
//pop up stack elements to ensure descending order!
while(!stack.isEmpty() && stack.peek() < t){
lastSmallerRoot = stack.pop();
}
stack.push(t);
}
}
return true;
}
3. Iteratively: Time: O(n), extra Space:O(1)!
public boolean verifyPreorder(int[] preorder) {
int lastSmallerRoot = Integer.MIN_VALUE;
//modify preorder[0-k] used as stack! Extra Space: O(1)!
int k = -1;
for(int i=0; i<preorder.length; i++){
int t = preorder[i];
if(t < lastSmallerRoot){
return false;
}
while(k >= 0 && t > preorder[k]){
lastSmallerRoot = preorder[k--];
}
preorder[++k] = t;
}
return true;
}
3. Iteratively: Time: O(n), extra Space:O(1)!
public boolean verifyPreorder(int[] preorder) {
int lastSmallerRoot = Integer.MIN_VALUE;
//modify preorder[0-k] used as stack! Extra Space: O(1)!
int k = -1;
for(int i=0; i<preorder.length; i++){
int t = preorder[i];
if(t < lastSmallerRoot){
return false;
}
while(k >= 0 && t > preorder[k]){
lastSmallerRoot = preorder[k--];
}
preorder[++k] = t;
}
return true;
}
No comments:
Post a Comment