题目描述

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

题解

写任意一个二叉搜索树的后序遍历序列出来分析：

二叉搜索树的定义是 左节点 < 根节点，右节点 > 根节点

对于后序遍历的序列T，最后一个元素X就是根节点 ，如果去掉X，那么T满足：

T可以分成两段，前一段 < X ，后一段 > X ， 且这两段都满足后序序列

完美的递归定义

递归思路：

  1. 确定root
  2. 遍历，找到第一个大于root的值的位置 , 则该位置左边是左子树，右边是右子树
  3. 遍历右子树，如果都大于 root，则满足二叉搜索树，否则 返回 false
  4. 分别判断左子树和右子树是否仍是二叉搜索树（递归1,2,3）
public boolean VerifySquenceOfBST(int[] sequence) {
    if (sequence.length == 0)
        return false;

    return isBST(sequence,0,sequence.length - 2);
}

public boolean isBST(int[] sequence,int lo ,int hi){
    if (lo >= hi)
        return true;

    int root = sequence[hi + 1];
    int i = lo;
    while (i < hi){
        if (sequence[i] < root)
            i++;
        else break;
    }

    int j = i+1;
    while (j <= hi){
        if (sequence[j++] < root)
            return false;
    }

    //递归左右子树
    return isBST(sequence,lo,i - 1) && isBST(sequence,i+1,hi -1);
}