作者:whisper
链接:https://www.proprogrammar.com/article/939
声明:请尊重原作者的劳动,如需转载请注明出处
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true
,否则返回 false
。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5 / \ 2 6 / \ 1 3
示例 1:
输入: [1,6,3,2,5] 输出: false
示例 2:
输入: [1,3,2,6,5] 输出: true
提示:
数组长度 <= 1000
难度:中等;标签:无;编程语言:JAVA
class Solution {
public boolean verifyPostorder(int[] postorder) {
return verifyPostorder(0, postorder.length - 1, Integer.MAX_VALUE+1l, postorder);
}
private boolean verifyPostorder(int start, int end, long p, int[] postorder){
if(start >= 0 && end > start){
int i = end - 1;
while(i >= start){
if(postorder[end] < postorder[i] && postorder[i] < p)i--;
else if(postorder[i] >= p)return false;
else break;
}
return verifyPostorder(start, i, postorder[end], postorder) && verifyPostorder(i + 1, end - 1, p, postorder);
}
return true;
}
}
自己写的一段时间自己又不会了,复习一下,中序是当前结点分成左右两部分,左边比当前小,右边比当前大,后序是当前结点分成左边两部分,左1比当前小,左2比当前大,据此,要有一个数进行比较,要分成两部分,从左到右,第一个大于最右(当前)结点的应该是左2的开始,左边是左1的结束,左1都小于当前结点,左2继续小于上一层结点
class Solution {
public boolean verifyPostorder(int[] postorder) {
int length = postorder.length;
if(length == 0) {
return true;
}
return verifyPostorder(postorder, 0, postorder.length -1);
}
private boolean verifyPostorder(int[] postorder, int startIndex, int endIndex) {
if(startIndex >= endIndex) {
return true;
}
int value = postorder[endIndex];
int rightIndex = startIndex;
while(postorder[rightIndex] < value) {
rightIndex++;
}
for(int i = rightIndex; i <= endIndex; i++) {
if(postorder[i] < value) {
return false;
}
}
return verifyPostorder(postorder, startIndex, rightIndex -1) && verifyPostorder(postorder, rightIndex, endIndex -1);
}
}
分成左1,左2两部分,左1比当前小,左2比当前大,然后左1,左2也是同样的情况
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论