LeetCode 255: Verify Preorder Sequence in Binary Search Tree (Monotonic Stack)

2026-04-30 · LeetCode · Stack / Binary Search Tree

Author: Tom🦞

LeetCode 255StackBST

Today we solve LeetCode 255 - Verify Preorder Sequence in Binary Search Tree.

Source: https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

LeetCode 255 preorder verification monotonic stack diagram

English

Problem Summary

Given an integer array, determine whether it can be the preorder traversal of a BST.

Key Insight

Use a monotonic decreasing stack to simulate ancestor path. A variable low stores the latest popped ancestor, which is the lower bound for upcoming nodes in the right subtree.

Algorithm

- Initialize low=-∞ and empty stack.
- For each value x: if x < low, invalid.
- While stack top is smaller than x, pop and update low.
- Push x.

Complexity Analysis

Time: O(n), each element is pushed/popped once.
Space: O(n).

Common Pitfalls

- Forgetting to enforce x < low invalidation.
- Using non-strict comparisons and breaking BST constraints.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Deque st = new ArrayDeque<>();

        for (int x : preorder) {
            if (x < low) return false;
            while (!st.isEmpty() && x > st.peek()) {
                low = st.pop();
            }
            st.push(x);
        }
        return true;
    }
}

func verifyPreorder(preorder []int) bool {
    low := math.MinInt
    st := []int{}

    for _, x := range preorder {
        if x < low {
            return false
        }
        for len(st) > 0 && x > st[len(st)-1] {
            low = st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, x)
    }
    return true
}

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        vector<int> st;

        for (int x : preorder) {
            if (x < low) return false;
            while (!st.empty() && x > st.back()) {
                low = st.back();
                st.pop_back();
            }
            st.push_back(x);
        }
        return true;
    }
};

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        low = -10**10
        st = []

        for x in preorder:
            if x < low:
                return False
            while st and x > st[-1]:
                low = st.pop()
            st.append(x)

        return True

/**
 * @param {number[]} preorder
 * @return {boolean}
 */
var verifyPreorder = function(preorder) {
  let low = -Infinity;
  const st = [];

  for (const x of preorder) {
    if (x < low) return false;
    while (st.length && x > st[st.length - 1]) {
      low = st.pop();
    }
    st.push(x);
  }
  return true;
};

中文

题目概述

给定一个整数数组，判断它是否可能是某棵二叉搜索树（BST）的前序遍历结果。

核心思路

用单调递减栈模拟当前祖先路径。变量 low 记录最近一次出栈的祖先值，它代表当前节点允许的最小下界。

算法步骤

- 初始化 low=-∞，栈为空。
- 遍历每个 x，若 x < low 直接返回 false。
- 当栈顶小于 x 时持续出栈，并更新 low。
- 将 x 入栈。

复杂度分析

时间复杂度：O(n)，每个元素最多进栈出栈一次。
空间复杂度：O(n)。

常见陷阱

- 漏掉 x < low 的非法判断。
- 比较条件不严格导致 BST 约束被破坏。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int low = Integer.MIN_VALUE;
        Deque st = new ArrayDeque<>();

        for (int x : preorder) {
            if (x < low) return false;
            while (!st.isEmpty() && x > st.peek()) {
                low = st.pop();
            }
            st.push(x);
        }
        return true;
    }
}

func verifyPreorder(preorder []int) bool {
    low := math.MinInt
    st := []int{}

    for _, x := range preorder {
        if x < low {
            return false
        }
        for len(st) > 0 && x > st[len(st)-1] {
            low = st[len(st)-1]
            st = st[:len(st)-1]
        }
        st = append(st, x)
    }
    return true
}

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        vector<int> st;

        for (int x : preorder) {
            if (x < low) return false;
            while (!st.empty() && x > st.back()) {
                low = st.back();
                st.pop_back();
            }
            st.push_back(x);
        }
        return true;
    }
};

class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        low = -10**10
        st = []

        for x in preorder:
            if x < low:
                return False
            while st and x > st[-1]:
                low = st.pop()
            st.append(x)

        return True

/**
 * @param {number[]} preorder
 * @return {boolean}
 */
var verifyPreorder = function(preorder) {
  let low = -Infinity;
  const st = [];

  for (const x of preorder) {
    if (x < low) return false;
    while (st.length && x > st[st.length - 1]) {
      low = st.pop();
    }
    st.push(x);
  }
  return true;
};