输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树：
5
/ \
2 6
/ \
1 3
示例 1：
输入: [1,6,3,2,5] 输出: false
示例 2：
输入: [1,3,2,6,5] 输出: true
提示：
数组长度 <= 1000
Related Topics
- 栈
- 树
- 二叉搜索树
- 递归
- 二叉树
- 单调栈
LeetCode刷题【剑指 Offer 33】二叉搜索树的后序遍历序列
分段验证
解题思路
分段验证
代码
class Solution {
public boolean verifyPostorder(int[] postorder) {
return validate(postorder,0,postorder.length-1);
}
private boolean validate(int[] postorder, int left ,int right){
//如果左指针大于等于右指针了，说明当前节点以及没有子节点了，自然是符合条件的】
if (left>=right || left < 0 || right < 0) return true;
//找到这段数组对应的根节点，根据后序遍历的特性，即为这段数组的最后一位
int rootNum = postorder[right];
//初始赋值
int leftEnd = -1;
int rightStart = -1;
//开始遍历
for (int i = left; i < right; i++) {
if (postorder[i] < rootNum){
//如果这个值小于根节点的值，说明这个节点应该是在左子树中
leftEnd = i;
}
if (postorder[i] > rootNum && rightStart == -1){
//如果这个值大于根节点的值，说明这个节点应该是右子树上的
//且rightStart == -1 表示是第一次碰到的
rightStart = i;
}
}
//此时如果符合条件的话，应该是 leftEnd 在 rightStart 的左边一位
//或者 没有左子树：leftEnd == -1 且rightStart == left
//或者 没有右子树：rightStart == -1 且leftEnd == right-1
boolean validateResult = (leftEnd>-1 && rightStart> -1 && leftEnd+1== rightStart)
|| ( leftEnd == -1 && rightStart == left )
|| ( rightStart == -1 && leftEnd == right-1);
//自身验证完了，还要对分割好了的子序列的有效性判断
if (validateResult){
return validate( postorder, left, leftEnd ) && validate( postorder, rightStart, right-1 );
}
return false;
}
}