剑指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])
}