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

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;
    }
}

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;
}