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)

Last updated