题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

golang 代码

func verifySequenceOfBST(seq []int) bool{
    return istree(seq, 0, len(seq)-1)
}

//输入序列
func istree(seq []int, left int, right int) bool {
    if left >= right {
        return true
    }
    var mid = -1
    for i := right - 1 ; i >= 0 ; i-- {
        //遇到左子树的根
        if seq[i] < seq[right] && mid == -1 {
            mid = i
        //左子树中有大于根的值
        }else if seq[i] > seq[right] && mid != -1 {
            return false
        }
    }
    //只有左子树或者只有右子树
    if mid == -1 || mid == right - 1 {
        return istree(seq, left, right-1)
    }else {
        return istree(seq, left, mid) && istree(seq, mid+1, right-1)
    }
}