示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读本文围绕《剑指 Offer第 2 版》面试题 33「二叉搜索树的后序遍历序列」展开给定一个整数数组判断它能否作为某棵二叉搜索树BST的后序遍历结果。文章完整继承 doocs/leetcode 仓库中 lcof/面试题33. 二叉搜索树的后序遍历序列/README.md 的题目背景、两种解法思路与全部多语言实现并结合仓库内Solution.*、Solution2.*源码逐行剖析算法机理。读完本文你将掌握「显式栈区间校验」与「单调栈反向遍历」两种判定范式理解二者在时间复杂度、空间复杂度上的差异并能直接复用仓库中 9 种编程语言的可用实现。题目概述如何判定一个数组是 BST 的后序遍历题目描述输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true否则返回false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树5 / \ 2 6 / \ 1 3示例 1输入: [1,6,3,2,5] 输出: false示例 2输入: [1,3,2,6,5] 输出: true提示数组长度 1000破题关键后序遍历 BST 双重性质判定算法依赖两条核心性质后序遍历特性遍历顺序为「左子树、右子树、根」因此数组的最后一个元素必为根节点二叉搜索树特性对于任意节点其左子树所有节点值均小于该节点右子树所有节点值均大于该节点题目假设元素互不相同因此不存在等于的情况。把这两条性质叠加可以得到一个可递归复用的局部判定规则取当前区间[l, r]postorder[r]为根从左往右扫描第一个不小于根值的位置i把区间切成三段——[l, i)是左子树段全部小于根、[i, r)是右子树段全部应大于根、r是根。只要右子树段中出现小于根的值即可判定非法。仓库中Solution.java、Solution.py、Solution.cpp、Solution.js、Solution.ts、Solution.rs、Solution.cs、Solution.swift、Solution.go均实现了基于该规则的两种算法对应 lcof/面试题33. 二叉搜索树的后序遍历序列 目录。方法一显式栈区间分治模拟递归为什么不用直接递归后序遍历的末元为根其左段应小于根、右段应大于根。数组长度可以到1000。考虑最坏情况——严格递增的数组例如[1,2,3,...,1000]递增序列里第一个不小于根的位置总在根的前一位第一次调用就是dfs(l, r-1)递归深度等于数组长度n会超出默认递归上限导致栈溢出。这就是「思考」环节点明直接递归不可行的根本原因。算法思路左右两段是否合法互不依赖调用顺序只要两段都检查过即可。因此可以把待查区间放进显式栈用循环替代递归初始区间为[0, n - 1]压栈弹出区间[l, r]若l r空区间或单元素直接跳过取v postorder[r]为根从l起向右找到第一个不小于v的位置i检查右段[i, r)若其中出现小于v的值返回false否则将右段[i, r-1]与左段[l, i-1]压栈继续循环栈空时所有区间均合法返回true。复杂度分析每个区间段在找分界点时需线性扫描最坏情况下每层都要扫一遍时间复杂度 $O(n^2)$栈中同时存放的区间个数与树高相关最坏为 $O(n)$空间复杂度 $O(n)$。其中 $n$ 为数组长度。多语言实现Python3源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.pyclass Solution: def verifyPostorder(self, postorder: List[int]) - bool: stk [(0, len(postorder) - 1)] while stk: l, r stk.pop() if l r: continue v postorder[r] i l while i r and postorder[i] v: i 1 if any(x v for x in postorder[i:r]): return False stk.append((i, r - 1)) stk.append((l, i - 1)) return TrueJava源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.java。注意这里用定长 int 数组 栈顶指针top模拟栈预先分配(n 2) * 2个槽位避免装箱开销出栈顺序与 Python 版一致先弹r再弹lclass Solution { public boolean verifyPostorder(int[] postorder) { int n postorder.length; int[] stk new int[(n 2) * 2]; int top 0; stk[top] 0; stk[top] n - 1; while (top 0) { int r stk[--top]; int l stk[--top]; if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk[top] i; stk[top] r - 1; stk[top] l; stk[top] i - 1; } return true; } }C源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.cpp。用vectorpairint, int保存区间配合结构化绑定auto [l, r]读取class Solution { public: bool verifyPostorder(vectorint postorder) { int n postorder.size(); vectorpairint, int stk{{0, n - 1}}; while (!stk.empty()) { auto [l, r] stk.back(); stk.pop_back(); if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk.emplace_back(i, r - 1); stk.emplace_back(l, i - 1); } return true; } };Go源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.go。用[][2]int切片保存区间stk stk[:len(stk)-1]模拟出栈func verifyPostorder(postorder []int) bool { n : len(postorder) stk : [][2]int{{0, n - 1}} for len(stk) 0 { cur : stk[len(stk)-1] stk stk[:len(stk)-1] l, r : cur[0], cur[1] if l r { continue } v : postorder[r] i : l for i r postorder[i] v { i } for j : i; j r; j { if postorder[j] v { return false } } stk append(stk, [2]int{i, r - 1}, [2]int{l, i - 1}) } return true }TypeScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.ts。用number[][]保存区间pop()!非空断言确保类型安全function verifyPostorder(postorder: number[]): boolean { const stk: number[][] [[0, postorder.length - 1]]; while (stk.length) { const [l, r] stk.pop()!; if (l r) { continue; } const v postorder[r]; let i l; while (i r postorder[i] v) { i; } for (let j i; j r; j) { if (postorder[j] v) { return false; } } stk.push([i, r - 1]); stk.push([l, i - 1]); } return true; }Rust源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.rs。注意 Rust 下标需as usize转换while let Some((l, r)) stk.pop()天然处理栈空退出impl Solution { pub fn verify_postorder(postorder: Veci32) - bool { let n postorder.len() as i32; let mut stk vec![(0, n - 1)]; while let Some((l, r)) stk.pop() { if l r { continue; } let v postorder[r as usize]; let mut i l; while i r postorder[i as usize] v { i 1; } for j in i..r { if postorder[j as usize] v { return false; } } stk.push((i, r - 1)); stk.push((l, i - 1)); } true } }JavaScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.js/** * param {number[]} postorder * return {boolean} */ var verifyPostorder function (postorder) { const stk [[0, postorder.length - 1]]; while (stk.length) { const [l, r] stk.pop(); if (l r) { continue; } const v postorder[r]; let i l; while (i r postorder[i] v) { i; } for (let j i; j r; j) { if (postorder[j] v) { return false; } } stk.push([i, r - 1]); stk.push([l, i - 1]); } return true; };C#源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.cs与 Java 版同为「定长数组 栈顶指针」写法public class Solution { public bool VerifyPostorder(int[] postorder) { int n postorder.Length; int[] stk new int[(n 2) * 2]; int top 0; stk[top] 0; stk[top] n - 1; while (top 0) { int r stk[--top]; int l stk[--top]; if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk[top] i; stk[top] r - 1; stk[top] l; stk[top] i - 1; } return true; } }Swift源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.swift。右段校验用切片postorder[i..r]的contains(where:)实现class Solution { func verifyPostorder(_ postorder: [Int]) - Bool { var stk [(0, postorder.count - 1)] while let (l, r) stk.popLast() { if l r { continue } let v postorder[r] var i l while i r postorder[i] v { i 1 } if i r postorder[i..r].contains(where: { $0 v }) { return false } stk.append((i, r - 1)) stk.append((l, i - 1)) } return true } }方法二单调栈反向遍历 父节点上界核心洞察反向看后序 「根、右、左」方法一用显式栈分段但每段仍要线性扫描最坏是平方时间。方法二换一个观察角度从右往左看后序顺序恰好是「根、右、左」。根据 BST 性质右子树所有节点值均大于根节点值。因此从右往左遍历数组就是从根节点往右子树走此时值逐渐变大直到遇到一个递减的节点——这个节点应该属于左子树。找到该节点的直接父节点后此后所有其它节点都必须小于该父节点否则返回false。单调栈维护「递减候选链」从源码结构看如 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.py栈中维护的是一个严格递减的候选链从右往左遍历时只要栈顶大于当前值就把栈顶弹出并更新上界mx——被弹出的栈顶正是当前节点的「直接父节点」候选。具体步骤如下初始化一个无穷大的父节点值上界mx以及一个空栈从右往左遍历数组对每个元素x如果x mx说明当前节点不满足 BST 性质它落在了某个左子树节点的右分支上却大于父节点返回false否则若栈不为空且栈顶元素大于x说明当前节点为左子树节点循环将栈顶元素出栈并赋值给mx直到栈为空或栈顶元素小于等于x然后将x入栈遍历结束后返回true。一次线性遍历即可完成判定时间复杂度 $O(n)$空间复杂度 $O(n)$。其中 $n$ 为数组长度。多语言实现Python3源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.py。mx inf使用 Python 内置正无穷postorder[::-1]完成反向遍历class Solution: def verifyPostorder(self, postorder: List[int]) - bool: mx inf stk [] for x in postorder[::-1]: if x mx: return False while stk and stk[-1] x: mx stk.pop() stk.append(x) return TrueJava源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.java。mx初始化为1 30大于题目取值范围的正大数充当无穷大用ArrayDeque作为栈class Solution { public boolean verifyPostorder(int[] postorder) { int mx 1 30; DequeInteger stk new ArrayDeque(); for (int i postorder.length - 1; i 0; --i) { int x postorder[i]; if (x mx) { return false; } while (!stk.isEmpty() stk.peek() x) { mx stk.pop(); } stk.push(x); } return true; } }C源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.cpp。注意此处直接reverse(postorder.begin(), postorder.end())原地反转后正向遍历与其它语言反向下标遍历等价class Solution { public: bool verifyPostorder(vectorint postorder) { stackint stk; int mx 1 30; reverse(postorder.begin(), postorder.end()); for (int x : postorder) { if (x mx) { return false; } while (!stk.empty() stk.top() x) { mx stk.top(); stk.pop(); } stk.push(x); } return true; } };Go源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.gofunc verifyPostorder(postorder []int) bool { mx : 1 30 stk : []int{} for i : len(postorder) - 1; i 0; i-- { x : postorder[i] if x mx { return false } for len(stk) 0 stk[len(stk)-1] x { mx stk[len(stk)-1] stk stk[:len(stk)-1] } stk append(stk, x) } return true }TypeScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.tsfunction verifyPostorder(postorder: number[]): boolean { let mx 1 30; const stk: number[] []; for (let i postorder.length - 1; i 0; --i) { const x postorder[i]; if (x mx) { return false; } while (stk.length stk[stk.length - 1] x) { mx stk.pop(); } stk.push(x); } return true; }JavaScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.js/** * param {number[]} postorder * return {boolean} */ var verifyPostorder function (postorder) { let mx 1 30; const stk []; for (let i postorder.length - 1; i 0; --i) { const x postorder[i]; if (x mx) { return false; } while (stk.length stk[stk.length - 1] x) { mx stk.pop(); } stk.push(x); } return true; };两种方法的对比与选型建议维度方法一显式栈区间分治方法二单调栈反向遍历遍历方向正向逐区间拆分反向从右往左核心数据结构栈中存区间对(l, r)栈中存递减候选节点值判定依据每个区间根值切分左/右段并校验右段弹出栈顶更新父节点上界mx出现大于mx的值即非法时间复杂度$O(n^2)$最坏每段线性扫描$O(n)$每个元素至多入栈、出栈一次空间复杂度$O(n)$$O(n)$递归风险无已用显式栈替代规避默认递归上限无纯迭代代码量略长更短、更精炼从算法竞赛与面试实战角度若追求思路直观、易于推导方法一更贴近「后序末元为根 左右子树区间校验」的自然递归定义适合作为第一反应给出若追求最优时间复杂度与极简代码方法二是首选它把「寻找直接父节点」这一操作用单调栈的弹栈过程摊销为 $O(1)$是典型的「反向遍历 单调栈」套路可迁移到其它树与栈结合的题目中题目提示数组长度可达1000两种方法都能通过但当数据规模增大时方法二的时间优势会体现得更加明显。仓库中两种方法的实现文件名规整方法一位于Solution.{py,java,cpp,go,ts,rs,js,cs,swift}其中cs、swift、rs仅方法一有方法二位于Solution2.{py,java,cpp,go,ts,js}可直接参考 lcof/面试题33. 二叉搜索树的后序遍历序列 目录对照学习。总结「二叉搜索树的后序遍历序列」是检验对BST 性质 后序遍历结构双重理解度的经典面试题。本文基于 doocs/leetcode 仓库的官方题解系统讲解了两种实现显式栈区间分治$O(n^2)$ 时间 / $O(n)$ 空间用栈替代递归拆解左右子树区间规避递增序列导致的递归栈溢出单调栈反向遍历$O(n)$ 时间 / $O(n)$ 空间从右往左以「根、右、左」视角推进用弹栈更新父节点上界实现单趟判定。两种算法均已在仓库中提供 Python、Java、C、Go、TypeScript、Rust、JavaScript、C#、Swift 等多语言实现读者可结合本文的逐行讲解与 lcof/面试题33. 二叉搜索树的后序遍历序列/README.md 及对应Solution*.源码深入验证。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐scrcpy 安卓投屏教程免费开源手机镜像到电脑 5 分钟跑通scrcpy 安卓投屏教程免费开源手机镜像到电脑 5 分钟跑通 scrcpy 是一个免费开源的安卓投屏工具通过 USB 或 Wi Fi 把手机屏幕镜像到电音视频InterviewGuide 剑指 Offer 刷题笔记 No23二叉搜索树的后序遍历序列递归判定详解与边界分析InterviewGuide 剑指 Offer 刷题笔记 No23二叉搜索树的后序遍历序列递归判定详解与边界分析 本篇技术指南来自 InterviewGu文档教程知识库剑指 Offer II 052. 展平二叉搜索树doocs/leetcode 中序遍历重连题解迭代与 DFS剑指 Offer II 052. 展平二叉搜索树doocs/leetcode 中序遍历重连题解迭代与 DFS 本文以 剑指 Offer II 052. 展示例工程上一篇M/o/Vfuscator编译器学术论文集近五年最佳研究成果下一篇Favicon加载策略终极指南预加载与懒加载最佳实践创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/16 1:59:21 · 阅读 1.2k 剑指 Offer 33「二叉搜索树的后序遍历序列」：显式栈与单调栈两种判定算法详解（doocs/leetcode 题解）
示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载导读本文围绕《剑指 Offer第 2 版》面试题 33「二叉搜索树的后序遍历序列」展开给定一个整数数组判断它能否作为某棵二叉搜索树BST的后序遍历结果。文章完整继承 doocs/leetcode 仓库中 lcof/面试题33. 二叉搜索树的后序遍历序列/README.md 的题目背景、两种解法思路与全部多语言实现并结合仓库内Solution.*、Solution2.*源码逐行剖析算法机理。读完本文你将掌握「显式栈区间校验」与「单调栈反向遍历」两种判定范式理解二者在时间复杂度、空间复杂度上的差异并能直接复用仓库中 9 种编程语言的可用实现。题目概述如何判定一个数组是 BST 的后序遍历题目描述输入一个整数数组判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true否则返回false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树5 / \ 2 6 / \ 1 3示例 1输入: [1,6,3,2,5] 输出: false示例 2输入: [1,3,2,6,5] 输出: true提示数组长度 1000破题关键后序遍历 BST 双重性质判定算法依赖两条核心性质后序遍历特性遍历顺序为「左子树、右子树、根」因此数组的最后一个元素必为根节点二叉搜索树特性对于任意节点其左子树所有节点值均小于该节点右子树所有节点值均大于该节点题目假设元素互不相同因此不存在等于的情况。把这两条性质叠加可以得到一个可递归复用的局部判定规则取当前区间[l, r]postorder[r]为根从左往右扫描第一个不小于根值的位置i把区间切成三段——[l, i)是左子树段全部小于根、[i, r)是右子树段全部应大于根、r是根。只要右子树段中出现小于根的值即可判定非法。仓库中Solution.java、Solution.py、Solution.cpp、Solution.js、Solution.ts、Solution.rs、Solution.cs、Solution.swift、Solution.go均实现了基于该规则的两种算法对应 lcof/面试题33. 二叉搜索树的后序遍历序列 目录。方法一显式栈区间分治模拟递归为什么不用直接递归后序遍历的末元为根其左段应小于根、右段应大于根。数组长度可以到1000。考虑最坏情况——严格递增的数组例如[1,2,3,...,1000]递增序列里第一个不小于根的位置总在根的前一位第一次调用就是dfs(l, r-1)递归深度等于数组长度n会超出默认递归上限导致栈溢出。这就是「思考」环节点明直接递归不可行的根本原因。算法思路左右两段是否合法互不依赖调用顺序只要两段都检查过即可。因此可以把待查区间放进显式栈用循环替代递归初始区间为[0, n - 1]压栈弹出区间[l, r]若l r空区间或单元素直接跳过取v postorder[r]为根从l起向右找到第一个不小于v的位置i检查右段[i, r)若其中出现小于v的值返回false否则将右段[i, r-1]与左段[l, i-1]压栈继续循环栈空时所有区间均合法返回true。复杂度分析每个区间段在找分界点时需线性扫描最坏情况下每层都要扫一遍时间复杂度 $O(n^2)$栈中同时存放的区间个数与树高相关最坏为 $O(n)$空间复杂度 $O(n)$。其中 $n$ 为数组长度。多语言实现Python3源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.pyclass Solution: def verifyPostorder(self, postorder: List[int]) - bool: stk [(0, len(postorder) - 1)] while stk: l, r stk.pop() if l r: continue v postorder[r] i l while i r and postorder[i] v: i 1 if any(x v for x in postorder[i:r]): return False stk.append((i, r - 1)) stk.append((l, i - 1)) return TrueJava源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.java。注意这里用定长 int 数组 栈顶指针top模拟栈预先分配(n 2) * 2个槽位避免装箱开销出栈顺序与 Python 版一致先弹r再弹lclass Solution { public boolean verifyPostorder(int[] postorder) { int n postorder.length; int[] stk new int[(n 2) * 2]; int top 0; stk[top] 0; stk[top] n - 1; while (top 0) { int r stk[--top]; int l stk[--top]; if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk[top] i; stk[top] r - 1; stk[top] l; stk[top] i - 1; } return true; } }C源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.cpp。用vectorpairint, int保存区间配合结构化绑定auto [l, r]读取class Solution { public: bool verifyPostorder(vectorint postorder) { int n postorder.size(); vectorpairint, int stk{{0, n - 1}}; while (!stk.empty()) { auto [l, r] stk.back(); stk.pop_back(); if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk.emplace_back(i, r - 1); stk.emplace_back(l, i - 1); } return true; } };Go源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.go。用[][2]int切片保存区间stk stk[:len(stk)-1]模拟出栈func verifyPostorder(postorder []int) bool { n : len(postorder) stk : [][2]int{{0, n - 1}} for len(stk) 0 { cur : stk[len(stk)-1] stk stk[:len(stk)-1] l, r : cur[0], cur[1] if l r { continue } v : postorder[r] i : l for i r postorder[i] v { i } for j : i; j r; j { if postorder[j] v { return false } } stk append(stk, [2]int{i, r - 1}, [2]int{l, i - 1}) } return true }TypeScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.ts。用number[][]保存区间pop()!非空断言确保类型安全function verifyPostorder(postorder: number[]): boolean { const stk: number[][] [[0, postorder.length - 1]]; while (stk.length) { const [l, r] stk.pop()!; if (l r) { continue; } const v postorder[r]; let i l; while (i r postorder[i] v) { i; } for (let j i; j r; j) { if (postorder[j] v) { return false; } } stk.push([i, r - 1]); stk.push([l, i - 1]); } return true; }Rust源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.rs。注意 Rust 下标需as usize转换while let Some((l, r)) stk.pop()天然处理栈空退出impl Solution { pub fn verify_postorder(postorder: Veci32) - bool { let n postorder.len() as i32; let mut stk vec![(0, n - 1)]; while let Some((l, r)) stk.pop() { if l r { continue; } let v postorder[r as usize]; let mut i l; while i r postorder[i as usize] v { i 1; } for j in i..r { if postorder[j as usize] v { return false; } } stk.push((i, r - 1)); stk.push((l, i - 1)); } true } }JavaScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.js/** * param {number[]} postorder * return {boolean} */ var verifyPostorder function (postorder) { const stk [[0, postorder.length - 1]]; while (stk.length) { const [l, r] stk.pop(); if (l r) { continue; } const v postorder[r]; let i l; while (i r postorder[i] v) { i; } for (let j i; j r; j) { if (postorder[j] v) { return false; } } stk.push([i, r - 1]); stk.push([l, i - 1]); } return true; };C#源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.cs与 Java 版同为「定长数组 栈顶指针」写法public class Solution { public bool VerifyPostorder(int[] postorder) { int n postorder.Length; int[] stk new int[(n 2) * 2]; int top 0; stk[top] 0; stk[top] n - 1; while (top 0) { int r stk[--top]; int l stk[--top]; if (l r) { continue; } int v postorder[r]; int i l; while (i r postorder[i] v) { i; } for (int j i; j r; j) { if (postorder[j] v) { return false; } } stk[top] i; stk[top] r - 1; stk[top] l; stk[top] i - 1; } return true; } }Swift源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution.swift。右段校验用切片postorder[i..r]的contains(where:)实现class Solution { func verifyPostorder(_ postorder: [Int]) - Bool { var stk [(0, postorder.count - 1)] while let (l, r) stk.popLast() { if l r { continue } let v postorder[r] var i l while i r postorder[i] v { i 1 } if i r postorder[i..r].contains(where: { $0 v }) { return false } stk.append((i, r - 1)) stk.append((l, i - 1)) } return true } }方法二单调栈反向遍历 父节点上界核心洞察反向看后序 「根、右、左」方法一用显式栈分段但每段仍要线性扫描最坏是平方时间。方法二换一个观察角度从右往左看后序顺序恰好是「根、右、左」。根据 BST 性质右子树所有节点值均大于根节点值。因此从右往左遍历数组就是从根节点往右子树走此时值逐渐变大直到遇到一个递减的节点——这个节点应该属于左子树。找到该节点的直接父节点后此后所有其它节点都必须小于该父节点否则返回false。单调栈维护「递减候选链」从源码结构看如 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.py栈中维护的是一个严格递减的候选链从右往左遍历时只要栈顶大于当前值就把栈顶弹出并更新上界mx——被弹出的栈顶正是当前节点的「直接父节点」候选。具体步骤如下初始化一个无穷大的父节点值上界mx以及一个空栈从右往左遍历数组对每个元素x如果x mx说明当前节点不满足 BST 性质它落在了某个左子树节点的右分支上却大于父节点返回false否则若栈不为空且栈顶元素大于x说明当前节点为左子树节点循环将栈顶元素出栈并赋值给mx直到栈为空或栈顶元素小于等于x然后将x入栈遍历结束后返回true。一次线性遍历即可完成判定时间复杂度 $O(n)$空间复杂度 $O(n)$。其中 $n$ 为数组长度。多语言实现Python3源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.py。mx inf使用 Python 内置正无穷postorder[::-1]完成反向遍历class Solution: def verifyPostorder(self, postorder: List[int]) - bool: mx inf stk [] for x in postorder[::-1]: if x mx: return False while stk and stk[-1] x: mx stk.pop() stk.append(x) return TrueJava源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.java。mx初始化为1 30大于题目取值范围的正大数充当无穷大用ArrayDeque作为栈class Solution { public boolean verifyPostorder(int[] postorder) { int mx 1 30; DequeInteger stk new ArrayDeque(); for (int i postorder.length - 1; i 0; --i) { int x postorder[i]; if (x mx) { return false; } while (!stk.isEmpty() stk.peek() x) { mx stk.pop(); } stk.push(x); } return true; } }C源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.cpp。注意此处直接reverse(postorder.begin(), postorder.end())原地反转后正向遍历与其它语言反向下标遍历等价class Solution { public: bool verifyPostorder(vectorint postorder) { stackint stk; int mx 1 30; reverse(postorder.begin(), postorder.end()); for (int x : postorder) { if (x mx) { return false; } while (!stk.empty() stk.top() x) { mx stk.top(); stk.pop(); } stk.push(x); } return true; } };Go源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.gofunc verifyPostorder(postorder []int) bool { mx : 1 30 stk : []int{} for i : len(postorder) - 1; i 0; i-- { x : postorder[i] if x mx { return false } for len(stk) 0 stk[len(stk)-1] x { mx stk[len(stk)-1] stk stk[:len(stk)-1] } stk append(stk, x) } return true }TypeScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.tsfunction verifyPostorder(postorder: number[]): boolean { let mx 1 30; const stk: number[] []; for (let i postorder.length - 1; i 0; --i) { const x postorder[i]; if (x mx) { return false; } while (stk.length stk[stk.length - 1] x) { mx stk.pop(); } stk.push(x); } return true; }JavaScript源码见 lcof/面试题33. 二叉搜索树的后序遍历序列/Solution2.js/** * param {number[]} postorder * return {boolean} */ var verifyPostorder function (postorder) { let mx 1 30; const stk []; for (let i postorder.length - 1; i 0; --i) { const x postorder[i]; if (x mx) { return false; } while (stk.length stk[stk.length - 1] x) { mx stk.pop(); } stk.push(x); } return true; };两种方法的对比与选型建议维度方法一显式栈区间分治方法二单调栈反向遍历遍历方向正向逐区间拆分反向从右往左核心数据结构栈中存区间对(l, r)栈中存递减候选节点值判定依据每个区间根值切分左/右段并校验右段弹出栈顶更新父节点上界mx出现大于mx的值即非法时间复杂度$O(n^2)$最坏每段线性扫描$O(n)$每个元素至多入栈、出栈一次空间复杂度$O(n)$$O(n)$递归风险无已用显式栈替代规避默认递归上限无纯迭代代码量略长更短、更精炼从算法竞赛与面试实战角度若追求思路直观、易于推导方法一更贴近「后序末元为根 左右子树区间校验」的自然递归定义适合作为第一反应给出若追求最优时间复杂度与极简代码方法二是首选它把「寻找直接父节点」这一操作用单调栈的弹栈过程摊销为 $O(1)$是典型的「反向遍历 单调栈」套路可迁移到其它树与栈结合的题目中题目提示数组长度可达1000两种方法都能通过但当数据规模增大时方法二的时间优势会体现得更加明显。仓库中两种方法的实现文件名规整方法一位于Solution.{py,java,cpp,go,ts,rs,js,cs,swift}其中cs、swift、rs仅方法一有方法二位于Solution2.{py,java,cpp,go,ts,js}可直接参考 lcof/面试题33. 二叉搜索树的后序遍历序列 目录对照学习。总结「二叉搜索树的后序遍历序列」是检验对BST 性质 后序遍历结构双重理解度的经典面试题。本文基于 doocs/leetcode 仓库的官方题解系统讲解了两种实现显式栈区间分治$O(n^2)$ 时间 / $O(n)$ 空间用栈替代递归拆解左右子树区间规避递增序列导致的递归栈溢出单调栈反向遍历$O(n)$ 时间 / $O(n)$ 空间从右往左以「根、右、左」视角推进用弹栈更新父节点上界实现单趟判定。两种算法均已在仓库中提供 Python、Java、C、Go、TypeScript、Rust、JavaScript、C#、Swift 等多语言实现读者可结合本文的逐行讲解与 lcof/面试题33. 二叉搜索树的后序遍历序列/README.md 及对应Solution*.源码深入验证。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐scrcpy 安卓投屏教程免费开源手机镜像到电脑 5 分钟跑通scrcpy 安卓投屏教程免费开源手机镜像到电脑 5 分钟跑通 scrcpy 是一个免费开源的安卓投屏工具通过 USB 或 Wi Fi 把手机屏幕镜像到电音视频InterviewGuide 剑指 Offer 刷题笔记 No23二叉搜索树的后序遍历序列递归判定详解与边界分析InterviewGuide 剑指 Offer 刷题笔记 No23二叉搜索树的后序遍历序列递归判定详解与边界分析 本篇技术指南来自 InterviewGu文档教程知识库剑指 Offer II 052. 展平二叉搜索树doocs/leetcode 中序遍历重连题解迭代与 DFS剑指 Offer II 052. 展平二叉搜索树doocs/leetcode 中序遍历重连题解迭代与 DFS 本文以 剑指 Offer II 052. 展示例工程上一篇M/o/Vfuscator编译器学术论文集近五年最佳研究成果下一篇Favicon加载策略终极指南预加载与懒加载最佳实践创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考