LeetCode 255. 验证二叉搜索树的前序遍历序列

Categories:

题目描述
思路分析
1. 解法一：单调栈（推荐）
相似题目

题目描述

✅ 255. 验证二叉搜索树的前序遍历序列

思路分析

解法一：单调栈（推荐）

核心思路：

使用栈维护递增序列，lower 记录当前允许的最小值。

当遇到比栈顶大的值时，说明进入右子树，弹栈更新 lower。

若当前值小于 lower，则不是合法前序。

复杂度分析：

时间复杂度：O(n)，其中 n 表示序列长度。

空间复杂度：O(n)，栈空间。

import java.util.ArrayDeque;
import java.util.Deque;

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

        for (int val : preorder) {
            if (val < lower) {
                return false;
            }

            while (!stack.isEmpty() && val > stack.peek()) {
                lower = stack.pop();
            }

            stack.push(val);
        }

        return true;
    }
}

func verifyPreorder(preorder []int) bool {
	stack := make([]int, 0)
	lower := -1 << 60

	for _, val := range preorder {
		if val < lower {
			return false
		}

		for len(stack) > 0 && val > stack[len(stack)-1] {
			lower = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}

		stack = append(stack, val)
	}

	return true
}

相似题目

题目	难度	考察点
255. 验证二叉搜索树的前序遍历序列	中等	单调栈
98. 验证二叉搜索树	中等	BST
1008. 前序遍历构造二叉搜索树	中等	BST
450. 删除二叉搜索树中的节点	中等	BST
449. 序列化和反序列化二叉搜索树	中等	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/90550795