# 题目链接
# 题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
例如,下图是后序遍历序列 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