255. Verify Preorder Sequence in Binary Search Tree

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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

Code

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        if(preorder == null || preorder.length == 0) return true;
        Stack<Integer> s = new Stack<>();

        int min = Integer.MIN_VALUE;

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

            while(!s.isEmpty() && s.peek() < num) {
                min = s.pop();
            }

            s.push(num);
        }

        return true;
    }
}

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stack = []
        min = float("-inf")

        for num in preorder:
            # 当前的min是之后点的最小值，所以不能出现num < min
            if num < min:
                return False

            # 如果num < stack.peek()说明当前还在左子树
            # 当num > stack.peek()时，说明已经到了右子树了
            # 此时需要找到当前点是哪个点的右子树，并且修改min，同时pop出stack中的值
            while len(stack) != 0 and num > stack[-1]:
                min = stack.pop()

            stack.append(num)

        return True