一、题目
- 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回
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^)/ ~ 「干货分享,每天更新」