255. 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.

一刷
题解：
具体的思路是，利用栈，实现preorder traversal。具体的措施是，压栈root, left, 如果是right，则弹出对应的left和root
Time complexity O(n), space complexity O(logn)

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

不使用Stack，Space Complexity O(1)的解法， 利用了原数组

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

二刷
还是忘记了。不用递归，perorder, inorder, postorder都要用栈实现。
Stack

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