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

一、题目

• 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

二、示例

2.1> 示例 1：

【输入】 [1,6,3,2,5]

【输出】 false

2.2> 示例 2：

【输入】 [1,3,2,6,5]

【输出】 true

提示：

• 0 <= 数组长度 <= 1000

三、解题思路

• 根据题目描述，我们要验证某个给定的数组是否是某个二叉搜索树的后序遍历，那么这里面有两个关键信息，分别是：

【关键点1】二叉搜索树；

【关键点2】后序遍历；

• 首先，我们先了解一下二叉搜索树的特性：

【若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值；

【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；

• 其次，我们了解一下后序遍历的特性：

【后序遍历】首先遍历左子树，然后遍历右子树，最后访问根结点。

• 好了，了解了上面的基本知识，我们就可以开始寻找解题规律了。由于题目中给我们的是数组，那么我们先假设这个数组是“合法”的通过针对某棵二叉搜索树后序遍历获得了。那么针对长度为m的数组postorder，它一定具有如下特征，即：

【左子树】postorder[0] ~ postorder[x]

【右子树】postorder[x+1] ~ postorder[m-2]

【根节点】postorder[m-1]

• 那么我们会得出以下结论：

• postorder[m-1]会 大于 所有postorder[0] ~ postorder[x]的值;
• postorder[m-1]会 小于 所有postorder[x+1] ~ postorder[m-2]的值；

• 那么，我们只要发现某一个元素不满足上面的两个结论，就可以直接判断不是合法的后序遍历。好了，解题思路就这么多了，下面我们还是举例演示一下，输入[1,3,2,6,5]，判断其是否是某个二叉搜索树的后序遍历。请见下图所示：

四、代码实现

classSolution {
publicbooleanverifyPostorder(int[] postorder) {
returnverify(postorder, 0, postorder.length-1);
    }
publicbooleanverify(int[] postorder, intstart, intend) {
if (start>=end) returntrue;
booleanbeginCheck=false;
intindex=start;
for (inti=end-1; i>=start; i--) {
if (!beginCheck&&postorder[i] <postorder[end]) {
beginCheck=true;
index=i;
            }
if (beginCheck&&postorder[i] >postorder[end]) returnfalse;
        }
returnverify(postorder, start, index) &&verify(postorder, index+1, end-1);
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」