题目描述

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

核心代码实现

public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if(sequence.length == 0){ return false; } return VerifySquOfBST(sequence, 0, sequence.length-1); } private static boolean VerifySquOfBST(int[] seq, int start, int end){ if(start >= end){ //递归终止条件,seq[start:end]序列中无元素或只有一个元素 return true; } //首先找到序列中第一个大于当前子树根节点的元素 int tempIndex = start; while(tempIndex<end && seq[tempIndex]<seq[end]){ tempIndex++; //tempIndex在右子树开始处 } //其次判断seq[tempIndex]之后的元素是否都大于当前子树根节点（seq[end]） for(int i=tempIndex+1; i<end; i++){ if(seq[i]<seq[end]){ return false; } } //继续判断左右子树的后序遍历序列是否也满足二叉搜索树“左节点<根<右节点”的特点 return VerifySquOfBST(seq, start, tempIndex-1) && VerifySquOfBST(seq, tempIndex, end-1); } }