面试题24：二叉搜索树的后序遍历序列

题目描述

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

代码实现

import java.util.Arrays;
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0)
            return false;
        int root = sequence[sequence.length-1];
        
        //在二叉搜索树中左子树的结点小于根结点
        int i = 0;
        for(;i < sequence.length-1;i++){
            if(sequence[i] > root)
                break;
        }
        
        //在二叉搜索树中右子树的结点大于根结点
        int j = i;
        for(;j < sequence.length-1;j++){
            if(sequence[j] < root)
                return false;
        }
        
        //判断左子树是不是二叉搜索树
        boolean left = true;
        if(i > 0){
            left = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));
        }
        
        //判断右子树是不是二叉搜索树
        boolean right = true;
        if(i < sequence.length-1){
            right = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, sequence.length-1));
        }
        
        return left && right;
        
    }
}

主要思路

1、二叉查找树，又叫二叉排序树，它或者是一棵空树，或者是具有下列性质的： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树
2、后序遍历序列的最后一个结点为根结点，数组中前面的数字分为两部分：前半部分是左子树结点的值，它们都比根结点小，后半部分是右子树结点的值，它们都比根结点大
3、截取数组的一部分用 Arrays.copyOfRange(sequence, 0, i)