题目描述

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

解析

  • 找到根结点
  • 从头遍历序列，第一个比根结点大的元素为右子树的起点
  • 判断右子树是否都比根结点大，若不是返回false，若是，进行下一步
  • 分别把左子树和右子树都以上面规则进行判断，若左右子树都能返回true，则整个序列为二叉搜索树的后序遍历序列，返回true

代码实现

  1. public boolean verifySquenceOfBST(int [] sequence) {
  3.     if(sequence == null || sequence.length == 0){
  4.         return false;
  5.     }
  7.     int len = sequence.length;
  8.     int root = sequence[len - 1];
  10.     int i = 0;
  11.     for(; i < len - 1; i++){
  12.         if(sequence[i] > root){
  13.             break;
  14.         }
  15.     }
  17.     int j = i;
  18.     for(;j < len - 1; j++){
  19.         if(sequence[j] < root){
  20.             return false;
  21.         }
  22.     }
  24.     boolean left = true;
  25.     boolean right = true;
  26.     if(i > 0){
  27.         left = verifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
  28.     }
  29.     if(i < len - 1){
  30.         right = verifySquenceOfBST(Arrays.copyOfRange(sequence,i,len - 1));
  31.     }
  33.     return left && right;
  34. }
  38. <p></p>