题目:输入一个整数数组，判断该数组是不是某二叉搜索树的先序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同.
<pre><code>`

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

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

var preData = [8,6,5,7,10,9,11]
result = searchTree.verifyPreDataOfBST(arr: preData)
if result {
print("(preData)是先序序列")
} else {
print("(preData)不是先序序列")
}

preData = [8,6,5,7]
result = searchTree.verifyPreDataOfBST(arr: preData)
if result {
print("(preData)是先序序列")
} else {
print("(preData)不是先序序列")
}

preData = [8,10,9,11]
result = searchTree.verifyPreDataOfBST(arr: preData)
if result {
print("(preData)是先序序列")
} else {
print("(preData)不是先序序列")
}

preData = [8,10,9,4]
result = searchTree.verifyPreDataOfBST(arr: preData)
if result {
print("(preData)是先序序列")
} else {
print("(preData)不是先序序列")
}

preData = [8,10,4,9]
result = searchTree.verifyPreDataOfBST(arr: preData)
if result {
print("(preData)是先序序列")
} else {
print("(preData)不是先序序列")
}`</code></pre>