题目:输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同.
实现方式1：
<pre><code>`
func verifyPostDataOfBST(arr:[Int]) -> Bool {
if arr.count == 0 {
return false
}

    if arr.count == 1 {
        return true
    }
    
    var leftIndex:Int = 0
    let root:Int = arr[arr.count-1] // 首位数字是根节点
    
    for m in 0..<arr.count-1 {
        leftIndex = m
        if  arr[m] > root {//左子树的节点都小于根节点
            break
        }
    }
    
    var rightIndex:Int = leftIndex
    for i in leftIndex..<arr.count-1 {
        rightIndex = i
        if arr[i] < root { // 右子树的节点都大于根节点
            break
        }
    }
    
    var data = arr
    let count:Int = arr.count
    
    if rightIndex == count-2 {
        // mid == right 只有左子树 mid = 0 arr[end-1] > arr[end] 只有右子树
        let isRight:Bool = (leftIndex == 0 && arr[count-2] > arr[count-1])
        if(leftIndex == rightIndex || isRight) { // 只有左子树或者只有右子树
            return verifyPostDataOfBST(arr: Array(data[leftIndex..<count-1]))
        } else if(leftIndex == 0) {
            return false
        } else {
            return verifyPostDataOfBST(arr: Array(data[0..<leftIndex])) && verifyPostDataOfBST(arr: Array(data[leftIndex..<arr.count-1]))
        }
    } else {
        return false
    }
}`</code></pre>

实现方式2：
<pre><code>`

func verifySquenceOfBST(arr:[Int]) -> Bool {

    if(0 == arr.count) {
        return false
    }
    return isPostOrder(arr: arr, begin: 0, end: arr.count-1);
}


func isPostOrder(arr:[Int],begin:Int,end:Int) -> Bool {
    if(begin == end) {
        return true;
    }
    
    var mid:Int = begin
    for i in 0..<end{
        mid = i
        if  arr[i] > arr[end] { //左子树的节点都小于根节点
            break
        }
    }
    var right:Int = mid
    for m in right..<end {
        right = m
        if arr[m] < arr[end] { // 右子树的节点都大于根节点
            break
        }
    }

    if right == end-1 {
        // mid == right 只有左子树 mid = 0 arr[end-1] > arr[end] 只有右子树
        let isRight:Bool = (mid == 0 && arr[end-1] > arr[end])
        if(mid == right || isRight) { // 只有左子树或者只有右子树
            return isPostOrder(arr: arr, begin:begin, end:end-1)
        } else if(mid == 0) {
            return false
        } else {
            return (isPostOrder(arr: arr, begin:begin, end:mid-1) && isPostOrder(arr: arr, begin:mid, end:end-1))
        }
    } else {
        return false
    }
}`</code></pre>

测试代码:
<pre><code>`

var postData:[Int] = [5,7,6,9,11,10,8]
var searchTree:BinarySearchTree = BinarySearchTree()
var result:Bool = false
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}

postData = [5,6,11,10,8]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}

postData = [7,4,6,5]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}

postData = [7,6,4,5]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}

postData = [2,3,1]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}

postData = [9,11,10,8]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}
//
postData = [5,7,6,8]
result = searchTree.verifyPostDataOfBST(arr: postData)
if result {
print("(postData)是后序序列")
} else {
print("(postData)不是后序序列")
}`</code></pre>

需要注意的是题目中的二叉搜索树不是满二叉树，左子树或者右子树都有可能为空.