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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param sequence int整型一维数组
 * @return bool布尔型
 */
// 二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树
// 后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历
func VerifySquenceOfBST(sequence []int) bool {
	// write code here
	// 约定空树不是二叉搜索树
	if len(sequence) == 0 {
		return false
	}

	return check(sequence, 0, len(sequence)-1)
}

func check(sequence []int, l, r int) bool {
	// 子树剩一个节点
	if l >= r {
		return true
	}

	root := sequence[r]

	// 代表左子树的最后一个索引位置
	var leftLast int
	// 找到左子树和右子树的分界点
	for leftLast = r; leftLast >= l; leftLast-- {
		if sequence[leftLast] < root {
			break
		}
	}

	// 判断左子树是否合法
	for i := leftLast; i >= l; i-- {
		if sequence[i] > root {
			return false
		}
	}

	return check(sequence, l, leftLast) && check(sequence, leftLast+1, r-1)
}