JZ33 二叉搜索树的后序遍历序列

描述

输入一个整数数组
    
    
   ，判断该数组是不是某二叉搜索树的后序遍历的结果    
    
    
。如果是则返回 true ,否则返回 false 


     


     


   。假设输入的数组的任意两个数字都互不相同

 




 




 

。 提示： 1.二叉搜索树是指父亲节点大于左子树中的全部节点     


     


     

，但是小于右子树中的全部节点的树   

   

   

。 2.该题我们约定空树不是二叉搜索树 3.后序遍历是指按照 “左子树-右子树-根节点    
    
    
” 的顺序遍历

思路

BST的后序序列的合法序列是 




 




 




，对于一个序列S

   

   

  ，最后一个元素是x （也就是根）     

     

     
，如果去掉最后一个元素的序列为T  




  




  




， 那么T满足：T可以分成两段


  


  


 ，前一段（左子树）小于x     
     
     ，后一段（右子树）大于x   




   




   




， 且这两段（子树）都是合法的后序序列  

     

     

  。完美的递归定义

代码

package mid.JZ33二叉搜索树的后序遍历序列; public class Solution { public boolean VerifySquenceOfBST(int [] sequence) { if (sequence == null || sequence.length == 0) return false; return judge(sequence, 0, sequence.length - 1); } public boolean judge(int[] sequence, int start, int end) { //为空 if (start >= end) return true; //根节点 int root = sequence[end]; int i = start; //左子树遍历 while (i <= end && sequence[i] < root) { i++; } //右子树 for (int j = i; j < end; j++) { if (sequence[j] < root) return false; } //左子树 与 右子树递归 /** * i 是右子树第一个元素 * 左侧 start开始



 



 



，i-1结束 * 右侧 i开始               ，end-1是减去当前根元素 */ return judge(sequence, start, i - 1) && judge(sequence, i, end - 1); } }