255. Verify Preorder Sequence in Binary Search Tree

255. Verify Preorder Sequence in Binary Search Tree

Medium

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.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

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

Example 2:

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

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

Accepted

32,826

Submissions

76,719

Seen this question in a real interview before?

-----------------------
Solution #1, O(n) time and space
stack里保证的是递增（从top到底下），遇到比top大说明是走到了右子树，然后把之前左子树跟root全部pop掉，取root为lower bound（之后再也不会遇到比这更小，如果有，说明顺序有错误）
这方法是模拟preorder traversal的iterative的版本

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

Solution #2 O(n) time, O(1) space, 把给定的preorder数组利用起来，当作stack来存