树9: 二进制搜索树的后序遍历

描述: 输入整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

想法（递归）:

在后遍历序列中，最后一个数字是树的根节点. 数组中的前一个数字可以分为两部分: 第一部分是左子树节点的值，该值小于根节点的值；第二部分是左子树节点的值. 第二部分是右子树节点的值，大于根节点的值，然后递归判断前后两个部分是否满足上述原理.

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length<=0) return false;
        return jude(sequence,0,sequence.length-1);
    }
    public boolean jude(int[] sequence,int start,int end){
        if(start>=end) return true;//要处理的数据只有一个或者已经没有数据要处理
        // 从左向右找第一个不小于根结点（sequence[end]）的元素的位置
        int index=start;
        while((index<end-1)&&(sequence[end]>sequence[index]))
            index++;
        int right=index;
        //到这 [start,index-1]<[end]
        //保证[index, end-1]的所有元素都是大于根根点的值
        while(index<end-1&&sequence[end]<sequence[index])
            index++;
        if(index!=end-1) return false;
        index=right;
        return jude(sequence,start,index-1)&&jude(sequence,index,end-1);
    }
}

递归方法的时间复杂度:

以标准的完美二叉搜索树为例，每个递归级别都涉及序列的遍历. 尽管层数越深二叉排序树的遍历，节点数越少（子树的根节点数越少），但是这种减少是微不足道的二叉排序树的遍历，即使在最低级别上，仍然存在n / 2个节点（第i层的节点数理想的二叉树是其上所有节点的总和+ 1），因此，每层递归方法的遍历成本为O（n），对于二叉树，递归层的平均数目为O（logn） ，因此，递归方法的最终复杂度为O（nlogn）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-238678-1.html