剑指Offer 33. 二叉搜索树的后序遍历序列
题目链接： 剑指Offer 33. 二叉搜索树的后序遍历序列
题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
解法思路：
既然是二叉搜索树，那就一定满足以下性质：
- 左子树 < 根 < 右子树;
- 在树的后序遍历中，根始终处于左右子树的最后；
因此每次递归时验证最后一个节点是不是合理的二叉搜索树根即可
代码：
func verifyPostorder(post []int) bool {
if len(post) == 0 {
return true
}
// 根节点
rootVal := post[len(post)-1]
idx := 0
// 二叉搜索树的左子树都小于根
for idx < len(post) && post[idx] < rootVal {
idx++
}
left := idx
// 二叉搜索树的右子树都大于根
for idx < len(post) && post[idx] > rootVal {
idx++
}
return idx == len(post)-1 && verifyPostorder(post[:left]) && verifyPostorder(post[left:len(post)-1])
}