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.

Example 1:

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

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

My Solutions:

此题和#98题很像，但是需要从数组中找到根节点、左子树和右子树。 按照#98的思路，从根节点开始每个节点维护一个范围，随着递归调用一直往下传递，只有所有数都落在指定范围内才是一棵有效二叉搜索树。

Time: O(n); Space: O(h), h = tree's height

public class Solution {
    int index; 
    public boolean verifyPreorder(int[] preorder) {
        helper(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
        return index == preorder.length;
    }

    private void helper(int[] preorder, int min, int max) {
        if (index == preorder.length) return;

        int val = preorder[index];
        if (min < val && val < max) {
            index++;
            helper(preorder, min, val);
            helper(preorder, val, max);
        }
    }
}

根据前序遍历的特点，根节点就是第一个数，如果找到第一个大于根节点值的数的位置，前半部就是左子树，右半部就是右子树。因此使用一个单调递减堆栈。

先设一个最小值low，然后遍历数组，如果当前值小于这个low，返回false。从数组第一个数开始只要是递减的就压入堆栈中，说明每个数都落在之前所有节点的左子树中。当碰到第一个比堆栈顶部大的数，说明当前这个数是堆栈中某一个节点的右子节点。此时弹出所有比这个数小的节点，并且更新low，然后把当前节点压入栈中。这样如果遍历完整个数组都没有返回false的话，返回true。

public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE;
    Stack<Integer> stack = new Stack<>();
    for (int p : preorder) {
        if (p < low) return false;
        while (!stack.isEmpty() && p > stack.peek()) low = stack.pop();
        stack.push(p);
    }
    return true;
}

这个方法还可以进一步优化，不使用 stack，直接修改 preorder，将 low 值存在 preorder 的特定位置，前提是不能影响当前的遍历。

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