LeetCode 剑指 Offer 33. 二叉搜索树的后序遍历序列

Categories:

Tags:

题目描述
思路分析
1. 解法一：递归分治（推荐）
2. 解法二：单调栈（逆后序遍历）
相似题目

题目描述

✅ 剑指 Offer 33. 二叉搜索树的后序遍历序列

思路分析

解法一：递归分治（推荐）

核心思路：

后序遍历的最后一个元素必然是当前子树的根节点。

根据 BST 性质：左子树所有节点值小于根，右子树所有节点值大于根。

从左向右扫描，找到第一个大于根的位置，该位置左侧为左子树，右侧（不含根）为右子树。

验证右子树区间内所有节点值必须全部大于根，否则不合法。

递归对左右子树区间重复以上过程，直到区间长度 ≤ 1 时返回 true。

复杂度分析：

时间复杂度：O(n²)，其中 n 表示数组长度，每层递归最坏情况下扫描整个区间

空间复杂度：O(n)，其中 n 表示递归调用栈深度，最坏情况（链状树）为 O(n)

class Solution {

    public boolean verifyPostorder(int[] postorder) {
        return verify(postorder, 0, postorder.length - 1);
    }

    private boolean verify(int[] postorder, int left, int right) {
        // 区间长度 <= 1，无需验证
        if (left >= right) {
            return true;
        }
        // 后序遍历最后一个元素为当前子树根节点
        int root = postorder[right];
        // 从左向右找第一个大于根的位置，即右子树起始位置
        int mid = left;
        while (mid < right && postorder[mid] < root) {
            mid++;
        }
        // 验证右子树区间内所有节点值必须大于根
        int temp = mid;
        while (temp < right) {
            if (postorder[temp] < root) {
                return false;
            }
            temp++;
        }
        // 递归验证左子树和右子树
        return verify(postorder, left, mid - 1) && verify(postorder, mid, right - 1);
    }
}

func verifyPostorder(postorder []int) bool {
	return verify(postorder, 0, len(postorder)-1)
}

func verify(postorder []int, left, right int) bool {
	// 区间长度 <= 1，无需验证
	if left >= right {
		return true
	}
	// 后序遍历最后一个元素为当前子树根节点
	root := postorder[right]
	// 从左向右找第一个大于根的位置，即右子树起始位置
	mid := left
	for mid < right && postorder[mid] < root {
		mid++
	}
	// 验证右子树区间内所有节点值必须大于根
	temp := mid
	for temp < right {
		if postorder[temp] < root {
			return false
		}
		temp++
	}
	// 递归验证左子树和右子树
	return verify(postorder, left, mid-1) && verify(postorder, mid, right-1)
}

解法二：单调栈（逆后序遍历）

核心思路：

后序遍历顺序为：左 → 右 → 根；将数组逆序后变为：根 → 右 → 左，即类似前序遍历的镜像。

维护一个单调递减栈，以及一个变量 parent 记录当前节点的父节点值（初始为正无穷）。

从右向左遍历数组（即逆后序方向），每遇到一个节点：

若当前节点值大于 parent，说明违反了 BST 性质，返回 false。

将栈中所有大于当前节点的元素弹出，最后弹出的元素即为当前节点的父节点，更新 parent。

将当前节点压栈。

利用 BST 性质：在逆后序遍历中，每次从右子树切换到左子树时，节点值会变小并穿越某个祖先，弹栈操作可精确定位这个祖先。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，每个元素最多入栈出栈各一次

空间复杂度：O(n)，其中 n 表示单调栈的最大存储空间

class Solution {

    public boolean verifyPostorder(int[] postorder) {
        Deque<Integer> stack = new ArrayDeque<>();
        // parent 表示当前节点必须小于的上界（父节点值），初始为正无穷
        int parent = Integer.MAX_VALUE;
        // 逆后序遍历：从右向左遍历数组
        for (int i = postorder.length - 1; i >= 0; i--) {
            int curr = postorder[i];
            // 当前节点值大于 parent，违反 BST 左子树约束
            if (curr > parent) {
                return false;
            }
            // 将所有大于当前节点的元素弹出，最后弹出的即为当前节点的父节点
            while (!stack.isEmpty() && stack.peek() > curr) {
                parent = stack.pop();
            }
            stack.push(curr);
        }
        return true;
    }
}

func verifyPostorder(postorder []int) bool {
	stack := make([]int, 0)
	// parent 表示当前节点必须小于的上界（父节点值），初始为最大整数
	parent := math.MaxInt64
	// 逆后序遍历：从右向左遍历数组
	for i := len(postorder) - 1; i >= 0; i-- {
		curr := postorder[i]
		// 当前节点值大于 parent，违反 BST 左子树约束
		if curr > parent {
			return false
		}
		// 将所有大于当前节点的元素弹出，最后弹出的即为当前节点的父节点
		for len(stack) > 0 && stack[len(stack)-1] > curr {
			parent = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, curr)
	}
	return true
}

相似题目

题目	难度	考察点
98. 验证二叉搜索树	中等	递归、二叉搜索树性质验证
255. 验证前序遍历序列二叉搜索树	中等	递归/单调栈、二叉搜索树验证
1008. 前序遍历构造二叉搜索树	中等	递归、二叉搜索树构造
96. 不同的二叉搜索树	中等	动态规划、二叉搜索树计数
106. 从中序与后序遍历序列构造二叉树	中等	递归、分治、后序遍历
剑指 Offer 7. 重建二叉树	中等	递归、分治、二叉树构造

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/97280527