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表示當(dāng)前遍歷完后樹的長度耐量，以便查看是否等于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)
}
//輔助棧,存儲值遞增的節(jié)點(diǎn)设联，每當(dāng)遇到值遞減的節(jié)點(diǎn) ri，則通過出棧來尋找節(jié)點(diǎn) ri的父節(jié)點(diǎn) root
func verifyPostorder(_ postorder: [Int]) -> Bool {
var arr = [Int]()
var root = Int.max
//后序遍歷翻轉(zhuǎn)遍歷：根-右-左
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!) {
//進(jìn)入左子樹颇象，并確定左子樹的根節(jié)點(diǎn)
root = arr.removeLast()
}
//添加新元素
arr.append(postorder[i])
}
return true
}
