剑指offer- 30.二叉搜索树（二叉排序树）的后序遍历(179)

30.二叉搜索树（二叉排序树）的后序遍历(179)

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

二叉搜索树（binary search tree BST）的概念：

? 二叉树排序树又称二叉搜索树，其定义为二叉排序树或者是空树，或者满足以下性质的二叉树：

? （1） 若根结点的左子树非空，则左子树上的所有结点关键字均小于根结点关键字。

? （2） 若根结点的右子树非空，则右子树上的所有结点关键字均大于根结点关键字。

? （3） 根结点的左、右子树本身又各是一颗二叉排序树。

• 思路：二叉搜索树的中序遍历序列是有序的。
  1. 后序遍历序列的最后一个值为该序列元素的中值，根据中值，找到左子树的位置（值 < 中值）。
  2. 然后判断其余元素是否都为二叉树的右子树（值 >中值），否则返回false。
  3. 递归判断左右子树。当序列元素只有两个或一个时，返回true。

package _30.二叉搜索树的后序遍历;
/*** 题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。* @author Administrator**/
public class PostOrderOfBST {
    public static boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence == null || sequence.length == 0) return false;return VerifySquenceOfBST(sequence,0,sequence.length-1);}public static boolean VerifySquenceOfBST(int [] sequence,int start,int end) {
    if(end - start <= 1) return true;int midData = sequence[end];int i = start;int index = 0;//找到左子树的位置while(sequence[i] < midData && i < end){
    i++;}//判断右子树的值是否都比mid大index = i;for(;i < end;i++){
    if(sequence[i] < midData)return false;}return VerifySquenceOfBST(sequence,start,i-1) && VerifySquenceOfBST(sequence,i,end-1);}public static void main(String[] args) {
    // 8// / \// 6 10// / \ / \// 5 7 9 11int[] data = {
    5,7,6,9,4,10,8};int[] data1 = {
    5,7,6,9,11,10,8};System.out.println(VerifySquenceOfBST(data));System.out.println(VerifySquenceOfBST(data1));}
}