题目

• https://blog.csdn.net/u013132035/article/details/80607000
• 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。

思路

• 在后序遍历得到的序列中，最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分：第一部分是左子树结点的值，它们都比根结点的值小；第二部分是右子树结点的值，它们都比根结点的值大。

• 以数组{5， 7， 6， 9， 11， 10， 8}为例，后序遍历的结果中最后一个值8就是根结点，在这个数组中前3个数字5，7， 6都比8小是根结点8的左子树结点；后3个数字9， 11， 10都比8大，是根结点8的右子树结点。

• 二叉树：

  • 满二叉树：从高到低，除了叶结点外，所有结点的左右结点都存在。

  • 完全二叉树：比满二叉树少几个叶结点，从左向右放子结点。

  • 平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。、

  • 二叉搜索树：空树或者二叉树的所有结点比它的左子结点大，比它的右子结点小

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        //如果数组的为空，则二叉搜索树直接为空
        if(sequence==null)
            return false;
        else{
            return VerifySequenceofBST_1(sequence,0,sequence.length-1);
        }
    }
    public boolean VerifySequenceofBST_1(int[] sequence,int begin,int end){
        if(begin>end)
            return false;
        //将根节点从数组中选择出来，数组最后一位是根节点
        int rootvalue = sequence[end];
        int len = 0;
        //这一步的是计算左子树的节点个数为多少个，左子树所有节点数值都是小于根节点的
        for(int i=0;i<end;i++){
            if(sequence[i]>rootvalue){
                break; 
            }
             len++;
        }
        //这一步是计算右子树的节点个数为多少，右子树的所有节点数值都大于根节点数值
        int len1 = len;
        for(int i=len1;i<end;i++){
            if(sequence[i]<rootvalue)
                break;
            len1++;
        }
        //如果最后右子树的值len1不等于end，意味着是在右子树中出现左子树的节点值，那么就混乱了
        if(len1!=end)
            return false;
        //对左子树这部分的数组再次进行递归
        boolean left = true;
        if(len>begin){
            left = VerifySequenceofBST_1(sequence,begin,len-1);
        }
        //对右子树部分的数组再次进行递归
        boolean right = true;
        if(len1<end){
            right = VerifySequenceofBST_1(sequence,len,len1-1);
        }
        //返回结果
        return (left && right);
    }
}