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

题目描述

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

分析

对于后序遍历。根节点位于末端，除去根节点后，对二叉搜索树而言其余数据可分为两段。前一段都小于根节点，即左子树。后一段都大于根节点，即右子树。且左右子树也为后序遍历序列。

• 首先从后往前遍历，找到第一个小于根节点的值。
• 该值右边即为右子树，左边及其本身即为左子树。递归判断即可。

实现

public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)
            return false;
        if(sequence.length == 1)
            return true;
        return search(sequence, 0, sequence.length-1);

    }
public boolean search(int[] a,int star,int root){
        if(star >= root)
            return true;
        int i = root;
        //从后面开始找
        while(i > star && a[i-1] > a[root])
            i--;//找到比根小的坐标
        //从前面开始找 star到i-1应该比根小
        for(int j = star;j < i - 1;j++)
            if(a[j] > a[root])
                return false;;
        return search(a, star, i-1) && search(a, i, root-1);
}