423 字
2 分钟
二叉搜索树的后序遍历序列
题目
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 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)}