# 题目链接
# 题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
例如，下图是后序遍历序列 1,3,2 所对应的二叉搜索树。
# 解题思路
- 因为是后序遍历，所以数组的最后一个元素为根节点；
- f为根节点下标，若根节点没有右子树，则所有的数都不会比postorder[f]大；然后在遍历数组的过程中，找到一个比根节点大的数，f为该节点下标，他可能为根节点的右子节点或右子节点的子节点...这不重要，重要的是，当i大于f时，已经遍历到了父节点（后续遍历：左子节点->右子节点->父节点），因为f为根节点右子节点（或右子节点的子节点...），所以若f为根节点的右子节点，则i为根节点；无论怎样，postorder[i]总是大于或等于根节点，若不满足这个条件，直接return false；
func verifyPostorder(postorder []int) bool {
if len(postorder) == 0 {
return true
}
f := len(postorder)-1//f为分割的位置
for i := 0; i < len(postorder); i++ {
if postorder[i] >= postorder[len(postorder)-1] {
f = i
}
if i > f && postorder[i] < postorder[len(postorder)-1] {
return false
}//不满足二叉查找树的情况
}
return verifyPostorder(postorder[:f]) && verifyPostorder(postorder[f:len(postorder)-1])
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15