题目描述

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

解题思路

如果一个数组是一个二叉搜索树的后序遍历结果，那么这个数组有以下特征：数组的最后一个元素是（子）树的根节点，前面的部分可以分为两个部分，前一部分的元素都小于最后一个元素值，后一部分都大于数组最后一个元素值，我们首先需要找到这个临界值，在判断前一部分的元素是否都小于数组末尾的值，接着分别对数组前两部分处理。

代码实现

  1. public class Solution {
  2.     public boolean VerifySquenceOfBST(int [] sequence) {
  3.         if (sequence == null || sequence.length <= 0) {
  4.             return false;
  5.         }
  6.         return verifySequenceOfBST(sequence, 0, sequence.length - 1);
  7.     }
  8.     public static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
  9.         if (start >= end) {
  10.             return true;
  11.         }
  12.         int index = start;
  13.         while (index < end - 1 && sequence[index] < sequence[end]) {
  14.             index++;
  15.         }
  16.         int right = index;
  17.         while (index < end - 1 && sequence[index] > sequence[end]) {
  18.             index++;
  19.         }
  20.         if (index != end - 1) {
  21.             return false;
  22.         }
  23.         index = right;
  24.         return verifySequenceOfBST(sequence, start, index - 1) && verifySequenceOfBST(sequence, index, end - 1);
  25.     }
  26. }