剑指offer-23、搜索⼆叉树的后序遍历序列
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个整数数组，判断该数组是不是某⼆叉搜索树的后序遍历的结果。如果是则返回true,否则返回false 。假设输⼊的数组的任意两个数字都互不相同。</p>
<p>提示：</p>
<ol>
<li>⼆叉搜索树是指⽗亲节点⼤于左⼦树中的全部节点，但是⼩于右⼦树中的全部节点的树。</li>
<li>该题我们约定空树不是⼆叉搜索树</li>
<li>后序遍历是指按照 “左⼦树-右⼦树-根节点” 的顺序遍历</li>
<li>参考下⾯的⼆叉搜索树，示例 1</li>
</ol>
<p>示例1</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301648862.jpeg" alt="" loading="lazy"></p>
<p>输⼊：<br>
返回值：true<br>
说明：是上图的后序遍历 ，返回true</p>
<h2 id="思路及解答">思路及解答</h2>
<p>需要判断给定的整数数组是否是某个二叉搜索树(BST)的后序遍历结果。二叉搜索树具有以下特性：</p>
<ul>
<li>左子树所有节点的值小于根节点的值</li>
<li>右子树所有节点的值大于根节点的值</li>
<li>左右子树也必须是二叉搜索树</li>
</ul>
<p>后序遍历的顺序是：左子树 → 右子树 → 根节点，因此数组的最后一个元素一定是根节点</p>
<h3 id="递归标准解法">递归（标准解法）</h3>
<p>注意是⼆叉搜索树，如果是后续遍历的话，那么应该最后⼀个元素是中间元素 mid ，前⾯的元素可以分为两部分，⼀部分⽐ mid ⼩，另⼀部分全部⽐ mid ⼤。如果破坏这个原则，那么就应该输出No 。采取分⽽治之的⽅法，分别递归检查左⼦树以及右⼦树：</p>
<ol>
<li><strong>确定根节点</strong>：后序遍历的最后一个元素是根节点</li>
<li><strong>划分左右子树</strong>：从数组开头找到第一个大于根节点的元素，该元素之前为左子树，之后到根节点前为右子树</li>
<li><strong>验证BST性质</strong>：右子树所有元素必须大于根节点</li>
<li><strong>递归验证</strong>：对左右子树重复上述过程</li>
</ol>
<pre><code class="language-java">public class Solution {
public boolean VerifySquenceOfBST(int[] postorder) {
if (postorder == null || postorder.length == 0) {
return false; // 空树不是BST
}
return verify(postorder, 0, postorder.length - 1);
}
private boolean verify(int[] postorder, int start, int end) {
if (start >= end) {
return true; // 单个节点总是BST
}
int root = postorder; // 根节点是最后一个元素
int i = start;
// 找到第一个大于根节点的元素，作为左右子树分界
while (i < end && postorder < root) {
i++;
}
// 检查右子树是否都大于根节点
for (int j = i; j < end; j++) {
if (postorder < root) {
return false;
}
}
// 递归检查左右子树
return verify(postorder, start, i - 1) && verify(postorder, i, end - 1);
}
}
</code></pre>
<ul>
<li>时间复杂度：O($n^2$)，n 为⼆叉树节点的个数，当树为链式时时间复杂度最坏为 O($n^2$)</li>
<li>空间复杂度：O(n)，当树为链式结构时，递归深度为 n</li>
</ul>
<h3 id="单调栈法">单调栈法</h3>
<p>利用单调栈和后序遍历的倒序特性：</p>
<ol>
<li><strong>逆序处理</strong>：后序遍历的逆序是"根→右→左"，类似于变种的前序遍历</li>
<li><strong>维护最小值</strong>：使用单调栈保持递增顺序，遇到较小值时弹出并更新最小值</li>
<li><strong>验证性质</strong>：确保当前元素不大于最小值（即违反BST性质）</li>
</ol>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654344.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654618.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654428.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654134.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654436.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654360.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654207.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654773.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654556.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202503301654235.png" alt="" loading="lazy"></p>
<pre><code class="language-java">public boolean verifyPostorder(int[] postorder) {
if (postorder == null || postorder.length == 0) {
return false;
}
Stack<Integer> stack = new Stack<>();
int max = Integer.MAX_VALUE; // 初始化最大值
// 从后往前遍历
for (int i = postorder.length - 1; i >= 0; i--) {
int current = postorder;
// 如果当前节点大于max，违反BST性质
if (current > max) {
return false;
}
// 弹出所有比当前节点大的元素，并更新max
while (!stack.isEmpty() && stack.peek() > current) {
max = stack.pop();
}
stack.push(current);
}
return true;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个元素最多入栈和出栈一次</li>
<li><strong>空间复杂度</strong>：O(n)，最坏情况下需要存储所有元素</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19042012
頁:
[1]