https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/description/
image.png
因为是先序的BST，就是先中间，再小，再大。先根，再左节点，再右节点。所以最大的一定在最后面。而且还有一个性质，开始时头结点的大小，可以把后面的分为个区间。前半区间都比头小，后半区间都比头大。如果分不出来则不是BST的PREORDER.
不断递归用这个套路。
public boolean verifyPreorder(int[] preorder) {
return help(preorder,0,preorder.length-1);
}
private boolean help(int[] pre,int s,int e) {
if(s>=e) return true;
int j = s+1;
int mid = pre[s];
while(j<=e){
if(pre[j]>mid) break;
j++;
}
for(int i = j; i<=e ; i++){
if(pre[i]<mid) return false;
}
return help(pre,s+1,j-1) &&help(pre,j,e);
}
follow up:
你可以用迭代的方式，并且用O 1的空间来实现吗？
首先说迭代，因为是递归改非递归，我们就想到栈。我们可以尝试用单调栈的特性，如把小于的数不断推入栈中，然后发现有一个数比栈顶大了，分析这个点在原图的位置明白，这就代表一个SUBTREE的左边全部遍历完了，来到了右边，这时我们就需要不断从栈里POP，直到POP到一个位置，比右边这个要大。那么我们就知道最后一个POP的必然是当前最小，之后再有出现比他小的，就说明不对了，依次类推。
public boolean verifyPreorder(int[] preorder) {
int min = Integer.MIN_VALUE;
Stack<Integer> st = new Stack<>();
for(int num : preorder){
if(num < min) return false;
while(!st.isEmpty() && num > st.peek()){
min = st.pop();
}
st.push(num);
}
return true;
}
下面再思考如何O1，那么肯定需要用原数组来模拟栈了，那么有些数用过后肯定就不要再用了。根据这个规律，我们需要一个指针，如果不断递减，指针后移。如果有大了，POP时指针前移。还需要另外一个指针只往后走每次拿没用过的数。就OK了。
public boolean verifyPreorder(int[] preorder) {
int min = Integer.MIN_VALUE;
int stack = 0;
for(int num : preorder){
if(num < min) return false;
while(stack!=0 && num > preorder[stack-1]){
min = preorder[--stack];
}
preorder[stack++] = num;
}
return true;
}
