255 Verify Preorder Sequence in Binary Search Tree

255. Verify Preorder Sequence in Binary Search Tree

1. Question

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.

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

2. Implementation

思路：前序遍历的规律是数组是先递减然后再递增，所以我们维护一个变量min和单调递减的stack，表示当前最小的数值，如果当前的数小于min则返回false。如果栈顶的数比当前的数小，则将min更新为栈顶的数。

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int min = Integer.MIN_VALUE;

        Stack<Integer> stack = new Stack<>();

        for (int num : preorder) {
            if (num < min) {
                return false;
            }

            while (!stack.isEmpty() && stack.peek() < num) {
                min = stack.pop();
            }
            stack.push(num);
        }
        return true;
    }
}

Follow up: 题目要求要constant space, 我们可以直接用原数组模拟stack

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int index = -1;
        int min = Integer.MIN_VALUE;

        for (int num : preorder) {
            if (num < min) {
                return false;
            }

            while (index >= 0 && preorder[index] < num) {
                min = preorder[index--];
            }
            preorder[++index] = num;
        }
        return true;
    }
}

3. Time & Space Complexity

时间都是O(n)，利用栈的话空间复杂度是O(n), follow-up的做法空间复杂度是O(1)