剑指Offer 24 二叉搜索树的后序遍历序列

题目描述

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

思路

后序遍历，最后一个数就是根节点，他的前面左部分，小于他的是左子树，大于他的是右子树；当满足后序遍历时，左子树在一边，右子树在另外一边；然后根节点向下移动；递归就出来了

根据上面说的，整个数组，和最后一个数比较的话，应该大于的在一边，小于在一边，所以我们可以逐个比较即可

代码

ps:空间浪费了,因为当时懒得多写一个函数，顺便练习一下数组的copy方法

static public boolean VerifySquenceOfBST(int [] sequence) {
     if (sequence==null||sequence.length<=0)
         return false;
      boolean flag = false;
      int i = 0,j;
      for (; i <sequence.length-1;i++)
      {
          if (sequence[i]>sequence[sequence.length-1])
              break;
      }
      for (j=i;j<sequence.length-1;j++)
      {
          if (sequence[j]<sequence[sequence.length-1])
              return false;
      }
      boolean left = true;
     if (i>0) {
         int leftarray[] = new int[i];
         System.arraycopy(sequence, 0, leftarray, 0, i);
         left = VerifySquenceOfBST(leftarray);
     }
      boolean right=true ;
     if (i<sequence.length-1) {
         int rightarray[] = new int[sequence.length - i-1];
         System.arraycopy(sequence, 0, rightarray, 0, sequence.length - i-1);
         right = VerifySquenceOfBST(rightarray);
     }
      return left&&right;
  }

不传数组，传指针的做法

public boolean VerifySquenceOfBST(int [] sequence) {
       if(sequence.length == 0) return false;
       return IsTreeBST(sequence, 0, sequence.length-1);
   }
   public boolean IsTreeBST(int [] sequence,int start,int end ){
       if(end <= start) return true;
       int i = start;
       for (; i < end; i++) {
           if(sequence[i] > sequence[end]) break;
       }
       for (int j = i; j < end; j++) {
           if(sequence[j] < sequence[end]) return false;
       }
       return IsTreeBST(sequence, start, i-1) && IsTreeBST(sequence, i, end-1);
   }

非递归的做法

public boolean VerifySquenceOfBST(int [] sequence) {
        int size = sequence.length;
       if (size==0)
           return false;
       int i = 0;
       /*
       从前往后，先是小于最后一位数
       然后大于最后一位数，最后再加一如果就是最后一位
       那么就说明满足后序遍历
       */
       while (--size>=0)
       {
               while (sequence[i++]<sequence[size]);
               while (i<size&&sequence[i++]>sequence[size]);
                   if (i<size)
                       return false;
           i=0;
       }
       return true;
   }

收获

对于递归，我们可以先写比如两种情况，左子树怎么怎么样，然后是右子树怎么怎么样；然后就是递归的部分了；比较有模板性；
数组的鲁棒性，一是检查是不是null，而是检查length是不是0；这是两个操作；

2017-03-26