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.

一刷
題解：
具體的思路是，利用棧，實(shí)現(xiàn)preorder traversal。具體的措施是，壓棧root, left, 如果是right，則彈出對(duì)應(yīng)的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)的解法， 利用了原數(shù)組

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都要用棧實(shí)現(xiàn)。
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;
    }
}