Links

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

题目

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
5
/ \
2 6
/ \
1 3
示例 1:
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
提示: 数组长度 <= 1000

什么是「二叉搜索树」

二叉搜索树(BST,Binary Search Tree),也称 二叉排序树二叉查找树
一颗二叉树,可以为空;如果不为空,满足以下性质:
  • 非空左子树的所有键值小于根节点的键值
  • 非空右子树的所有键值大于根节点的键值
  • 左、右子树都是二叉搜索树

分析

知道了 二叉搜索树 的特性我们可以知道,它的后序遍历的结果结构为
  • 左节点集合A 右节点集合B 根节点 元素这样分布的数组
  • A 的所有元素小于跟节点, B 的所有元素大于跟节点
  • AB 也都是 二叉搜索树,这里就可以通过递归解决了,将问题转化为所有子树的后序遍历结果是否符合要求

解法

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