I don't know if my solution is a general one (I mean if you ask follow up questions like verify the postorder sequence or something). But it works for this one.
Idea: 1 What's the current lower bound value ?
if current value is smaller than current lower bound, return false.
2 When does the current lower bound value change ?
every time we jump from left branch to right branch.
case 1: we jump from left to right but we still stay at global left
case 2: we jump from left to right but we jump to the global right
public boolean verifyPreorder(int[] preorder) {
int l = preorder.length;
if (l == 0) return true;
int mark_min = Integer.MIN_VALUE;
int mark_max = preorder[0];
int pos = 1;
while (pos < l) {
while (pos < l && preorder[pos] < preorder[pos  1]) {
if (preorder[pos] < mark_min) return false;
pos += 1;
}
if (pos < l) {
if (preorder[pos] > mark_max) {
mark_min = mark_max;
mark_max = preorder[pos];
} else {
mark_min = preorder[pos  1];
}
}
pos += 1;
}
return true;
}
Java Solution. No stack and No change preorder values. O(n) time and O(1) space


Thank you so much. Yes, u r right~ My code is wrong but it passes all the 59 test cases. We find a lost test case LOL~ I have contacted the admin to check it out. @1337c0d3r