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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/33.-er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.