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