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

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
}