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

考点：栈、树

题目描述

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

代码格式

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {        
    }
}

二叉搜索树：（又：二叉查找树，二叉排序树）具有下列性质
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。

image.png

解题
1.思路
如上图：后序遍历是，左右根：[1,4,7,6,3,13,14,10,8]，可以知道根结点是8，再结合图再从左往右分析后序序列，分析子树，可以发现：

• [1,4,7,6,3] 8 [13,14,10]
• 左子树 ：[1,4] 3 [7,6]
• 左子树：10 [13,14]
  ......

本题是利用递归思想，判断根节点的左子树元素是否小于根节点，右子树元素是否大于根节点。重点在于对左右子树的划分（因为传入的是个数组）
（1）从第0位开始，找到第一位比根节点大的元素，记录此位置i。在此位置之前都属于左子树（此时已经断定左子树都小于根节点）
（2）检查右子树是否都大于根节点（从第i位开始，到根节点前）
（3）判断左右子树是否都属于二叉搜索树。
2.代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0){
            return false;
        }
        //调用getResult方法
        boolean result=getResult(sequence,0,sequence.length-1);
        return result;     
    }
    
    //定义一个getResult（）方法
    public boolean getResult(int[] s,int start,int end){
        int i=0;
        int j=0;
        if(end-start<=1){
            return true;
        }
        for(i=start;i<end;i++){
            if(s[i]>s[end]){
                break;
            }
        }
        
        for(j=i;j<end;j++){
            if(s[j]<s[end]){
                return false;
            }
        }
        
        boolean left=true;
        boolean right=true;
        if(i>0){
            left=getResult(s,start,i-1);
        }
        if(i<s.length-1){
            right=getResult(s,i,end-1);
        }
        
        return left&&right;
    }
}