题解 | #二叉搜索树的后序遍历序列#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param sequence int整型一维数组 
 * @return bool布尔型
*/
func VerifySquenceOfBST( sequence []int ) bool {
    // write code here
    // 后序遍历的最后一个节点一定是根节点
    // 前面部分分别是左子树 or 右子树
    // 先找左子树部分（找到第一个大于根节点的节点下标）
    // 再在右子树部分遍历（如果出现比根节点小的元素，返回 false，右子树值全部大于根节点）
    // 继续判断左子树部分、右子树部分是否满足（递归处理）

    if len(sequence) == 0 {
        return false 
    }

    if len(sequence) == 1 {
        return true
    }

    root := sequence[len(sequence)-1]

    // left
    i := 0
    for i < len(sequence)-1 { //不需要考虑根节点
        if sequence[i] > root {
            break
        }

        i++
    }

    // right 用 j 作为右子树的遍历指针
    j := i
    for j < len(sequence)-1 {
        if sequence[j] < root {
            return false
        }

        j++
    }
    // 如果遍历到没有左右子树，那么说明已经判断的部分都是符合条件的
    left, right := true, true
    if i > 0 {
        left = VerifySquenceOfBST(sequence[:i])
    }
    if i < len(sequence)-1 {
        right = VerifySquenceOfBST(sequence[i:len(sequence)-1])
    }
    
    return left && right
}