https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
//递归
func verifyPostorder(_ postorder: [Int]) -> Bool {
return verify(postorder, 0, postorder.count - 1)
}
func verify(_ nums: [Int], _ i: Int, _ j: Int) -> Bool {
if i >= j {return true}
//l表示当前遍历完后树的长度，以便查看是否等于j
var l = i
//左子树
while nums[l] < nums[j] {
l = l + 1
}
//右子树
var r = l
while nums[l] > nums[j] {
l = l + 1
}
return (l == j) && verify(nums, i, r - 1) && verify(nums, r, j - 1)
}
//辅助栈,存储值递增的节点，每当遇到值递减的节点 ri，则通过出栈来寻找节点 ri的父节点 root
func verifyPostorder(_ postorder: [Int]) -> Bool {
var arr = [Int]()
var root = Int.max
//后序遍历翻转遍历：根-右-左
for i in stride(from: postorder.count - 1, to: -1, by: -1) {
if postorder[i] > root {return false}
while (!arr.isEmpty && postorder[i] < arr.last!) {
//进入左子树，并确定左子树的根节点
root = arr.removeLast()
}
//添加新元素
arr.append(postorder[i])
}
return true
}
