Java Solution. No stack and No change preorder values. O(n) time and O(1) space

• ``````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;
}``````

• There is bug in your logic. e.g. for a non-BST such as [6,4,1,2,5,3] (look at the position of 4 and 3), your code judges it as true.

``````            ---- 6
/
4
/       \
1          5
\         /
2      3``````

• 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

• Thanks! I have just added the test case.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.