> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/stack/255-verify-preordersequence-in-binary-search-tree.md).

# 255    Verify Preorder Sequence in Binary Search Tree

## 255. [Verify Preorder Sequence in Binary Search Tree](https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/description/)

## 1. Question

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?

## 2. Implementation

思路：前序遍历的规律是数组是先递减然后再递增，所以我们维护一个变量min和单调递减的stack，表示当前最小的数值，如果当前的数小于min则返回false。如果栈顶的数比当前的数小，则将min更新为栈顶的数。

```java
public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int min = Integer.MIN_VALUE;

        Stack<Integer> stack = new Stack<>();

        for (int num : preorder) {
            if (num < min) {
                return false;
            }

            while (!stack.isEmpty() && stack.peek() < num) {
                min = stack.pop();
            }
            stack.push(num);
        }
        return true;
    }
}
```

Follow up: 题目要求要constant space, 我们可以直接用原数组模拟stack

```java
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int index = -1;
        int min = Integer.MIN_VALUE;

        for (int num : preorder) {
            if (num < min) {
                return false;
            }

            while (index >= 0 && preorder[index] < num) {
                min = preorder[index--];
            }
            preorder[++index] = num;
        }
        return true;
    }
}
```

## 3. Time & Space Complexity

时间都是O(n)，利用栈的话空间复杂度是O(n), follow-up的做法空间复杂度是O(1)