问题描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。
思路：
1.首先后序遍历的结果是[(左子树的后序)(右子树的后序)根结点]，那么我们首先找到了根结点的值, 2.其次，我们知道二叉搜索树的性质是：任何结点的左子树的值小于根结点的值，小于右子树的值。 3.因此，从后向前遍历，找到第一个小于root.val的，下标为index, 若index == n-1(n为数组的长度),则显然不满足，返回false， 否则我们可以将数组划分出来[(左子树的后序)(右子树的后序)根结点]。 4.最后对左右子树递归的判断即可。(但是这里要注意左子树或右子树为空的情况)
代码：
public boolean VerifySquenceOfBST(int [] sequence) { if(sequence == null || sequence.length == 0){ return false; } int n = sequence.length; if(n == 1 || n == 2){ return true; } int index = -1; for(int i = n-2; i >= 0; i--){ if(sequence[i] < sequence[n-1]){ index = i; break; } } int[] left = new int[index+1]; int[] right = new int[n-2-index]; for(int i = 0; i <= index; i++){ if(sequence[i] > sequence[n-1]){ return false; } left[i] = sequence[i]; } for(int i = index+1; i< n-1; i++){ right[i-index-1] = sequence[i]; } if(index == n - 2 && left.length != 0){ return VerifySquenceOfBST(left); } if(left.length == 0){ return VerifySquenceOfBST(right); } if(right.length == 0){ return VerifySquenceOfBST(left); } return VerifySquenceOfBST(left) && VerifySquenceOfBST(right); }转载于:https://www.cnblogs.com/wenbaoli/p/5655710.html
