題目:輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的先序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同.
<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] // 首位數(shù)字是根節(jié)點(diǎn)
    let count:Int = arr.count
    for i in 1..<count {
        leftIndex = i
        if  arr[i] > root { //左子樹的節(jié)點(diǎn)都小于根節(jié)點(diǎn)
            break
        }
    }
    
    var rightIndex:Int = leftIndex
    for i in leftIndex..<count {
        rightIndex = i
        if arr[i] < root { // 右子樹的節(jié)點(diǎn)都大于根節(jié)點(diǎn)
            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>

測(cè)試代碼:
<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>