Leetcode 255 Verify Preorder Sequence in Binary Search Tree

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?

Solution 1: Use iterative pre-order traversal.

 public class Solution {  
   public boolean verifyPreorder(int[] preorder) {  
     int n=preorder.length;  
     int i=0, lo=Integer.MIN_VALUE;  
     Deque<Integer> stack=new LinkedList<>();  
     while (i<n) {  
       if (stack.isEmpty() || preorder[i]<stack.peek()) {  
         if (preorder[i]<=lo) return false;  
         stack.push(preorder[i++]);  
       }  
       else if (preorder[i]==stack.peek()) return false;  
       else lo=stack.pop();  
     }  
     return true;  
   }  
 }