255. Verify Preorder Sequence in Binary Search Tree

use recursion

preorder, so root left right, right must be larger than root, or it's false

T: O(nlogn), logn is the tree height

S: O(nlogn)

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        return dfs(preorder, 0, preorder.length - 1);
    }
    private boolean dfs(int[] preorder, int start, int end) {
        if (start > end) {
            return true;
        }
        int root = preorder[start];
        int i = start + 1;
        while (i <= end && preorder[i] < root) {
            i++;
        }
        for (int right = i; right <= end; right++) {
            if (root > preorder[right]) {
                return false;
            }
        }
        return dfs(preorder, start + 1, i-1) && dfs(preorder, i, end);
    }
}

/*
use recursion 
T: O(nlogn)
S: O(nlogn)
*/

2. use mono stack

T: O(n)

S: O(n)

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Deque<Integer> stack = new ArrayDeque<>();
        int maxA = Integer.MIN_VALUE;
        
        for (int pre : preorder) {
            if (pre < maxA) {
                return false;
            }
            
            while (!stack.isEmpty() && pre > stack.peek()) {
                maxA = Math.max(maxA, stack.peek());
                stack.pop();
            }
            stack.push(pre);
        }
        return true;
    }
}

/*
a
max_a [......b.......][......c......]

if this is a preoder, when we find a < b, update max_a, we need max_a < c for every c after b

max_a < b && max_a < c => true, or is false

use mono stack to find max_a, 

so maintain a descreasing mono stack, when we meet larger one, means we got a < b
so pop a, update max(a, max_a)...

others just push a into stack

and in the following step, if we can find a new number is smaller than max_a, return false

T: O(n)
S: O(n)

*/