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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param sequence int整型一维数组 
 * @return bool布尔型
*/
var count = 0
func VerifySquenceOfBST( sequence []int ) bool {
	// write code here
	//fmt.Println("count=", count)
	//count++
    if count == 0 && len(sequence) ==0 {
        return false
    } else {
        count++
    }
	Len := len(sequence)
    if Len <= 1 {
		return true
	}
	//fmt.Println("Len=", Len)
	key := sequence[Len-1]
	i := 0
	//找到首次比根节点大的节点，则该节点左侧为左子树，右侧为右子树
	for i = 0; i < len(sequence); i++ {
		//fmt.Println(sequence[i])
		//fmt.Println("key=", key)
		if sequence[i] > key {
			break
		}
	}
    if i == len(sequence) {
        return true
    }
	//fmt.Println("i=", i)
	//判断右子树均大于根节点
	for j := i; j < Len; j++ {
		if sequence[j] < sequence[Len-1] {
			return false
		}
	}
	return VerifySquenceOfBST(sequence[:i]) && VerifySquenceOfBST(sequence[i:Len-1])
}