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.

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?

2. Implementation

(1) Method 1

思路: preorder 是一个先递减再递增的顺序,维护一个单调递减栈,当前num如果大于栈顶数时,则更新min,如果当前num小于min则该序列并不是preorder序列

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> stack = new Stack();

        int min = Integer.MIN_VALUE;

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

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

3. Time & Space Complexity

Method 1: 时间复杂度 O(n), 空间复杂度O(n)

Last updated

Was this helpful?