0255. Verify Preorder Sequence in Binary Search Tree

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree

Description

Given an array of unique integers preorder, return true if it is the correct preorder traversal sequence of a binary search tree.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= preorder.length <= 104

• 1 <= preorder[i] <= 104

• All the elements of preorder are unique.

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

ac1: stack, O(n) space

essential idea: right sub-tree always > parent node. very hard to come up with that.

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // edge cases
        if (preorder.length < 2) return true;

        // walk
        Stack<Integer> stack = new Stack<Integer>();
        int parent = Integer.MIN_VALUE;
        for (int i = 0; i < preorder.length; i++) {
            if (preorder[i] <= parent) return false;

            while (stack.size() > 0 && preorder[i] > stack.peek()) {
                parent = stack.pop();
            }

            stack.push(preorder[i]);
        }

        // pass test, true
        return true;
    }
}

ac2: utilize original array

Key point: using array like a stack.

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // edge cases
        if (preorder.length < 2) return true;

        // walk
        int parent = Integer.MIN_VALUE;
        for (int i = 0, j = 0; i < preorder.length; i++) {
            if (preorder[i] <= parent) return false;

            while (j > 0 && preorder[i] > preorder[j-1]) {
                parent = preorder[--j];
            }

            preorder[j++] = preorder[i];
        }

        // pass test, true
        return true;
    }
}