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

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

      5
     / \
    2   6
   / \
  1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示： 数组长度 <= 1000

来源：力扣（LeetCode）

什么是「二叉搜索树」

二叉搜索树（BST，Binary Search Tree），也称 二叉排序树 或 二叉查找树。

一颗二叉树，可以为空；如果不为空，满足以下性质：

• 非空左子树的所有键值小于其根节点的键值

• 非空右子树的所有键值大于其根节点的键值

• 左、右子树都是二叉搜索树

分析

知道了 二叉搜索树 的特性我们可以知道，它的后序遍历的结果结构为

• 左节点集合A 右节点集合B 根节点 元素这样分布的数组

• 且 A 的所有元素小于跟节点， B 的所有元素大于跟节点

• 而 A 、 B 也都是 二叉搜索树，这里就可以通过递归解决了，将问题转化为所有子树的后序遍历结果是否符合要求

解法

func verifyPostorder(_ postorder: [Int]) -> Bool {
    guard let root = postorder.last else {
        return true
    }
    var left: [Int] = []
    var right: [Int] = []
    var flag = false

    for offset in 1..<postorder.count {
        let v = postorder[postorder.count - 1 - offset]
        if v < root {
            if flag == false { flag = true }
            left.insert(v, at: 0)
        }
        else if v > root, flag == false {
            right.insert(v, at: 0)
        }
        else {
            return false
        }
    }

    return verifyPostorder(left) && verifyPostorder(right)
}