255. Verify Preorder Sequence in Binary Search Tree ----------M !!!!!~~~~~~

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.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up:
Could you do it using only constant space complexity?

A:

每次找到小于的， 然后分开查询

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        return helper(preorder, 0, preorder.size()-1);
    }
private:
    bool helper(vector<int>& preorder, int start, int end){
        if(start >= end) // just one value
            return true;
        int val = preorder[start];
        int mid = start+1; // mid point to first position either go-beyond, or with bigger value 
        while(mid<=end && preorder[mid] < val){
            mid++;
        }
        for(int i = mid; i<=end;i++){
            if(preorder[i] < val )
                return false;
        }
        return helper(preorder, start+1,mid-1) && helper(preorder, mid, end);
    }
};

上面这个方法，说都通过了，可是有点儿慢。   修改下，加上范围. 这样，可以省掉上面的for循环

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        return helper(preorder, 0, preorder.size()-1, INT_MIN, INT_MAX);
    }
private:
    bool helper(vector<int>& preorder, int start, int end, int lower, int upper){
        if(start > end) // just one value
            return true;
        int val = preorder[start];
        if(val <=lower || val >= upper)
            return false;
        if(start == end)
            return true;
        int mid = start+1; // mid point to first position either go-beyond, or with bigger value 
        while(mid<=end && preorder[mid] < val){
            if(preorder[mid]<=lower)
                return false;
            mid++;
        }
        return helper(preorder, start+1,mid-1, lower, val) && helper(preorder, mid, end, val, upper);
    }
};

这次通过了， 可是，只是faster than 5.65% 

观察得知，我们还是有了个while 循环，考虑去掉。  用stack 来表示。

This problem is very interesting. Recursive approach is very 
straightforward, though solution is likely of O(nlogn)/O(logn) 
time/space complexity (avg), or O(N^2)/O(N) worst case.

The key to optimize is to recall how iterative(non-recursive) 
pre-order traversal works, then follow the same idea to "reconstruct" 
BST from preorder sequence, during which we need a stack to keep track 
of node path from root. The trick here is to use input preorder sequence
 to simulate the stack in-place.  For verification purpose, we need to 
maintain a "lower bound" variable: when we visit a node that is the 
right child of its parent, the parent's value must be lower bound of all
 subsequent values.

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> st;
        int lower_bound = INT_MIN;
        for(int i = 0;i< preorder.size();i++){
            int v = preorder[i];
            if(v <= lower_bound) // check that it's in the range
                return false;
            
            if(st.empty() || v < st.top()){
                st.push(v);
            }else{
                lower_bound = st.top();
                st.pop();
                i--;     // this is the KEY, step back so we can check with grandparent 
            }
        }
        return true;
    }
};

Mistakes: