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?

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

维护一个单调递减的stack，当遇到递增的时候说明已经到了某个parent 的right subtree，并且不会在走比parent小的点，因此维护一个pre 值，来记录去right subtree之前的转折点。

  public boolean verifyPreorder(int[] preorder) {  
     Stack<Integer> desc = new Stack<>();  
     int pre = Integer.MIN_VALUE;  
     for(int i = 0; i < preorder.length; i++){  
       if(preorder[i] < pre) return false;  
       while(!desc.empty()&&preorder[i] > desc.peek()){  
           pre = desc.pop();  
       }  
       desc.push(preorder[i]);  
     }  
     return true;  
   }  

Solution 2 ... O(1) extra space

Same as above, but abusing the given array for the stack.

把preorder这个array当作stack来维护，用一个指针，如果是push，那么就是copy val到指针位置，并且向右移动指针，如果是pop 就像左移动指针。

public boolean verifyPreorder(int[] preorder) {
    int min = Integer.MIN_VALUE, i = -1;
    for (int val : preorder) {
        if (val < min)
            return false;
        while (i >= 0 && val > preorder[i])
            min = preorder[i--];
        preorder[++i] = val;
    }
    return true;
}