33. 二叉搜索树的后序遍历序列.md

解题思路

1. 递归分治

在树的后序遍历中，根始终处于左右子树的最后 而在二叉搜索树中，根始终大于左子树，且小于右子树 根据上面两个条件，每次递归时验证最后一个节点是不是合理的二叉搜索树根即可

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