Leetcode - Verify Preorder Sequence in Binary Search Tree

[分析]
思路1：暴力法，遍历当前待检查数组，找到第一个大于数组起始位置的位置i，则 i 为右子树根节点，然后递归判断左右子树。对于根节点，最坏情况下要遍历整个数组，时间为O（N），因为要递归检查每个节点，因此总的时间复杂度是O（N^2）。
思路2：参考StefanPochmann大神的作品https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space, 时间复杂度是O（N），空间复杂度是O（h）。

public class Solution {
    // Method 2
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) return true;
        LinkedList<Integer> stack = new LinkedList<Integer>();
        int low = Integer.MIN_VALUE;
        for (int i = 0; i < preorder.length; i++) {
            if (preorder[i] < low) return false;
            while (!stack.isEmpty() && preorder[i] > stack.peek()) {
                low = stack.pop();
            }
            stack.push(preorder[i]);
        }
        return true;
    }
    
    // Method 1: brute force
    public boolean verifyPreorder1(int[] preorder) {
        if (preorder == null) return false;
        return recur(preorder, 0, preorder.length - 1);
    }
    public boolean recur(int[] preorder, int start, int end) {
        if (start >= end) return true;
        int i = start + 1;
        while (i <= end && preorder[i] < preorder[start])
            i++;
        if (!recur(preorder, start + 1, i - 1))
            return false;
        int rightStart = i;
        while (i <= end && preorder[i] > preorder[start])
            i++;
        if (i <= end) return false;
        return recur(preorder, rightStart, end);
    }
}