# 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.

Consider the following binary search tree:

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

## Example

**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?

## Note

模拟一个二叉搜索树的前序遍历，利用其特性进行栈的迭代写法

左边一直走值都是一直减小的，一直压入栈；当遇到比它大的，说明遇到了前序遍历的某个右子树，右节点一定大于根节点大于左节点，连续pop，到这个根节点的父节点。同时记录`low`为最后pop出的节点，这个节点必须比当前前序遍历遇到的`curr`小

In place：利用修改当前的输入数组来代替栈

## Code

```java
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();

        for (int curr : preorder) {
            if (curr < low) {
                return false;
            }
            while (!stack.isEmpty() && curr > stack.peek()) {
                low = stack.pop();
            }
            stack.push(curr);
        }

        return true;
    }
}
```

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