第二十二题：二叉搜索树的后序遍历序列

 

题目描述

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

 

 

思路：递归和非递归的方式

 

          递归：

                    ①找到根节点

                    ②找到第一个比根节点大的结点为分解结点

                    ③判断条件：分界结点到根节点之间的数都比根节点要大

                    ④左右孩子树分而治之

       非递归：

                    利用二叉搜树的特性任意节点的左子树不大于根节点，右子树不小于根节点

                    ①找到根节点

                    ②判断数组前的所有数字都比根节点小或者大

                    ③使用index做为遍历数组的角标

                    ④index < 根节点的位置        说明不符合特性

 

 

具体实现如下图所示：

 

递归版本：

 

 

非递归版本：

 

 

 

具体实现代码如下：

/**
*〈一句话功能简述〉<br>
*〈二叉搜索树的后序遍历〉
*〈输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。〉
*
* @author 一个鲁肃
* @create 2018/8/14
* @since 1.0.0
*/
public class VerifySquenceOfBST {

    /**
     * 功能描述: <br>
     *〈非递归版本〉
     *
     * @param：sequence
     * @return: boolean
     */
    public boolean verifySquenceOfBST1(int [] sequence) {
        int size = sequence.length;
        //代码的鲁棒性
        if (size == 0){
            return false;
        }
        //定义指针变量
        int i = 0;
        while (--size > 0){
            while (sequence[i] < sequence[size]){
                i++;
            }
            while (sequence[i] > sequence[size]){
                i++;
            }
            //特性判断
            if (i < size) {
                return false;
            }
            i = 0;
        }
        return true;
    }

    /**
     * 功能描述: <br>
     *〈递归版本〉
     *  采取分治思想,左子树<根<=右子树
     *     首先找到根节点，二叉树的后序遍历最后一个节点就是根节点
     *     然后从头遍历找到第一个比根节点大的数字，此时分为左子树和右子树，进行分治判断
     *
     * @param：sequence
     * @return: boolean
     */
    public boolean verifySquenceOfBST2(int [] sequence) {
        //代码的鲁棒性
        if (sequence == null || sequence.length == 0){
            return false;
        }
        return judge(sequence,0,sequence.length-1);
    }
    //判断方法  
    public boolean judge(int[] arr,int start,int end){
        //递归的结束条件
        if (start >= end){
            return true;
        }
        //找到第一个比根节点大的结点
        int index = start;
        while (arr[index] < arr[end]){
            index++;
        }
        //该结点往后的结点都比根节点大
        for (int i = index;i < end;i++){
            if (arr[i] < arr[end]){
                return false;
            }
        }
        //分而治之
        return judge(arr,start,index-1) && judge(arr,index,end-1);
    }

}