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

## 题目

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

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

```
      5
     / \
    2   6
   / \
  1   3
```

示例 1：

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

示例 2：

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

提示： 数组长度 <= 1000

来源：[力扣（LeetCode）](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof)

## 什么是「二叉搜索树」

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

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

* `非空左子树`的所有键值`小于`其`根节点`的键值
* `非空右子树`的所有键值`大于`其`根节点`的键值
* `左、右子树`都是`二叉搜索树`

## 分析

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

* `左节点集合A 右节点集合B 根节点` 元素这样分布的数组
* 且 `A` 的所有元素小于跟节点， `B` 的所有元素大于跟节点
* 而 `A` 、 `B` 也都是 `二叉搜索树`，这里就可以通过递归解决了，将问题转化&#x4E3A;***所有子树的后序遍历结果是否符合要求***

## 解法

```swift
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)
}
```