Leetcode #255. Verify Preorder Sequence in Binary Search Tree

[yokostan]

Recursive:

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) return true;
        return helper(preorder, 0, preorder.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean helper(int[] preorder, int start, int end, int min, int max) {
        if (start >= end) return true;

        int root = preorder[start];
        for (int i = start + 1; i <= end; i++) {
            if (preorder[i] < min || preorder[i] > max) return false;
            if (preorder[i] > root) {
                return helper(preorder, start + 1, i - 1, min, root) && helper(preorder, i, end, root, max);
            }
        }

        return helper(preorder, start + 1, end, min, root);
    }
}

Stack:

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) return true;
        int low = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<Integer>();
        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;
    }
}

[yokostan]

reference for Stack: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/discuss/68142/Java-O(n)-and-O(1)-extra-space