二叉搜索树的后序遍历序列

1. 题目描述

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

2. 思路

• 最后一个元素是root，分成两半，确定左半<=root，右半>root

3. 实现

func VerifySquenceOfBST(sequence []int) bool {
	left := 0
	right := len(sequence) - 1
	return verifySquenceOfBST(sequence, left, right)

}

// 左闭右闭
func verifySquenceOfBST(sequence []int, left int, right int) bool {
	if left >= right {
		return true
	}
	//用最后一个节点（根节点）把数组分成两部分，前半部分<root，右半部分>root。
	root := sequence[right]
	var mid int
	for mid = left; mid < right; mid++ {
		if sequence[mid] > root {
			break
		}
	}
	//验证右半部分是否全部>root，否则返回false
	for i := mid; i < right; i++ {
		if sequence[i] <= root {
			return false
		}
	}
	//递归左半部分和右半部分
	return verifySquenceOfBST(sequence, left, mid-1) && verifySquenceOfBST(sequence, mid, right-1)
}

4. 参考

• 二叉搜索树的后序遍历序列_牛客网